Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "product of graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 21
Tytuł:
3-Tuple Total Domination Number of Rook’s Graphs
Autorzy:
Pahlavsay, Behnaz
Palezzato, Elisa
Torielli, Michele
Powiązania:
https://bibliotekanauki.pl/articles/32361755.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k -tuple total domination
Cartesian product of graphs
rook’s graph
Vizing’s conjecture
Opis:
A k-tuple total dominating set (kTDS) of a graph G is a set S of vertices in which every vertex in G is adjacent to at least k vertices in S. The minimum size of a kTDS is called the k-tuple total dominating number and it is denoted by γ×k,t(G). We give a constructive proof of a general formula for γ×3,t(Kn□Km).
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 15-37
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on the Thue Chromatic Number of Lexicographic Products of Graphs
Autorzy:
Peterin, Iztok
Schreyer, Jens
Škrabul’áková, Erika Fecková
Taranenko, Andrej
Powiązania:
https://bibliotekanauki.pl/articles/31342285.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
non-repetitive colouring
Thue chromatic number
lexicographic product of graphs
Opis:
A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r1r2⋯r2n such that ri = rn+i for all 1 ≤ i ≤ n). Let G be a graph whose vertices are coloured. A colouring ϕ of the graph G is non-repetitive if the sequence of colours on every path in G is non-repetitive. The Thue chromatic number, denoted by π(G), is the minimum number of colours of a non-repetitive colouring of G. In this short note we present two general upper bounds for the Thue chromatic number for the lexicographic product G ◦ H of graphs G and H with respect to some properties of the factors. One upper bound is then used to derive the exact values for π(G ◦ H) when G is a complete multipartite graph and H an arbitrary graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 635-643
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Constant Sum Partition of Sets of Integers and Distance Magic Graphs
Autorzy:
Cichacz, Sylwia
Gőrlich, Agnieszka
Powiązania:
https://bibliotekanauki.pl/articles/31342439.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
constant sum partition
distance magic labeling
product of graphs
Opis:
Let $ A = {1, 2, . . ., tm+tn} $. We shall say that $A$ has the $(m, n, t)$-balanced constant-sum-partition property ($(m, n, t)$-BCSP-property) if there exists a partition of $A$ into $2t$ pairwise disjoint subsets $ A^1, A^2, ... , A^t, B^1, B^2, ... , B^t$ such that $ | A^i | = m $ and $ | B^i | = n $, and $ \Sigma_{ a \in A^i } \ a = \Sigma_ {b \in B^j} \ b $ for $ 1 \le i \le t $ and $ 1 \le j \le t $. In this paper we give sufficient and necessary conditions for a set $A$ to have the $(m, n, t)$-BCSP-property in the case when $m$ and $n$ are both even. We use this result to show some families of distance magic graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 97-106
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge-Transitive Lexicographic and Cartesian Products
Autorzy:
Imrich, Wilfried
Iranmanesh, Ali
Klavžar, Sandi
Soltani, Abolghasem
Powiązania:
https://bibliotekanauki.pl/articles/31340755.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-transitive graph
vertex-transitive graph
lexicographic product of graphs
Cartesian product of graphs
Opis:
In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao [11]. For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 857-865
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with Clusters Perturbed by Regular Graphs—Aα-Spectrum and Applications
Autorzy:
Cardoso, Domingos M.
Pastén, Germain
Rojo, Oscar
Powiązania:
https://bibliotekanauki.pl/articles/31546556.pdf
Data publikacji:
2020-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cluster
convex combination of matrices
corona product of graphs
Aα-spectrum
Opis:
Given a graph G, its adjacency matrix A(G) and its diagonal matrix of vertex degrees D(G), consider the matrix Aα(G) = αD(G) + (1 − α)A(G), where α ∈ [0, 1). The Aα -spectrum of G is the multiset of eigenvalues of Aα(G) and these eigenvalues are the α-eigenvalues of G. A cluster in G is a pair of vertex subsets (C, S), where C is a set of cardinality |C| ≥ 2 of pairwise co-neighbor vertices sharing the same set S of |S| neighbors. Assuming that G is connected and it has a cluster (C, S), G(H) is obtained from G and an r-regular graph H of order |C| by identifying its vertices with the vertices in C, eigenvalues of Aα(G) and Aα(G(H)) are deduced and if Aα(H) is positive semidefinite, then the i-th eigenvalue of Aα(G(H)) is greater than or equal to i-th eigenvalue of Aα(G). These results are extended to graphs with several pairwise disjoint clusters (C1, S1), . . ., (Ck, Sk). As an application, the effect on the energy, α-Estrada index and α-index of a graph G with clusters when the edges of regular graphs are added to G are analyzed. Finally, the Aα-spectrum of the corona product G ◦ H of a connected graph G and a regular graph H is determined.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 2; 451-466
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
How Long Can One Bluff in the Domination Game?
Autorzy:
Brešar, Boštan
Dorbec, Paul
Klavžar, Sandi
Košmrlj, Gašpar
Powiązania:
https://bibliotekanauki.pl/articles/31341979.pdf
Data publikacji:
2017-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination game
game domination number
bluff graphs
minus graphs
generalized Petersen graphs
Kneser graphs
Cartesian product of graphs
Hamming graphs
Opis:
The domination game is played on an arbitrary graph G by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs K(n, 2), n ≥ 6, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 2; 337-352
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Minimal rankings of the Cartesian product Kₙ ☐ Kₘ
Autorzy:
Eyabi, Gilbert
Jacob, Jobby
Laskar, Renu
Narayan, Darren
Pillone, Dan
Powiązania:
https://bibliotekanauki.pl/articles/743282.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph colorings
rankings of graphs
minimal rankings
rank number
arank number
Cartesian product of graphs
rook's graph
Opis:
For a graph G = (V, E), a function f:V(G) → {1,2, ...,k} is a k-ranking if f(u) = f(v) implies that every u - v path contains a vertex w such that f(w) > f(u). A k-ranking is minimal if decreasing any label violates the definition of ranking. The arank number, $ψ_r(G)$, of G is the maximum value of k such that G has a minimal k-ranking. We completely determine the arank number of the Cartesian product Kₙ ☐ Kₙ, and we investigate the arank number of Kₙ ☐ Kₘ where n > m.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 725-735
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Motion planning in Cartesian product graphs
Autorzy:
Deb, Biswajit
Kapoor, Kalpesh
Powiązania:
https://bibliotekanauki.pl/articles/30148104.pdf
Data publikacji:
2014-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
robot motion in a graph
Cartesian product of graphs
Opis:
Let $G$ be an undirected graph with $n$ vertices. Assume that a robot is placed on a vertex and $n − 2$ obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path between the source and destination vertices in graph $G$. In this article we show that the path traced by the robot coincides with a shortest path in case of Cartesian product graphs. We give the minimum number of moves required for the motion planning problem in Cartesian product of two graphs having girth 6 or more. A result that we prove in the context of Cartesian product of $P_n$ with itself has been used earlier to develop an approximation algorithm for ($n^2 − 1$)-puzzle
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 2; 207-221
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Nearly perfect sets in products of graphs
Autorzy:
Kwaśnik, M.
Perl, M.
Powiązania:
https://bibliotekanauki.pl/articles/2050769.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
dominating sets
product of graphs
Opis:
The study of nearly perfect sets in graphs was initiated in [2]. Let $S \subseteq V(G)$. We say that $S$ is a nearly perfect set (or is nearly perfect) in $G$ if every vertex in $V(G) - S$ is adjacent to at most one vertex in $S$. A nearly perfect set $S$ in $G$ is called maximal if for every vertex $u \in V(G) - S, S \cup \{u\}$ is not nearly perfect in $G$. The minimum cardinality of a maximal nearly perfect set is denoted by $n_{p}(G)$. It is our purpose in this paper to determine maximal nearly perfect sets in two well-known products of two graphs, i.e. in the Cartesian product and in the strong product. Lastly, we give upper bounds of $n_{p}(G1 \times G2)$ and $n_{p}(G1 \otimes G2)$, for some special graphs $G1,G2$.
Źródło:
Opuscula Mathematica; 2004, 24, 2; 177-180
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Nearly perfect sets in the n-fold products of graphs
Autorzy:
Perl, M.
Powiązania:
https://bibliotekanauki.pl/articles/255571.pdf
Data publikacji:
2007
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
dominating sets
product of graphs
Opis:
The study of nearly perfect sets in graphs was initiated in [2], Let S ⊆ V(G). We say that S is a nearly perfect set (or is nearly perfect) in G if every vertex in V(G) - S is adjacent to at most one vertex in S. A nearly perfect set S in G is called 1-maximal if for every vertex u ∈ V(G) - S, S ∪ {u} is not nearly perfect in G. We denote the minimum cardinality of a 1-maximal nearly perfect set in G by np(G). We will call the 1-maximal nearly perfect set of the cardinality np(G) an np(G) - set. In this paper, we evaluate the parameter np(G) for some n-fold products of graphs. To this effect, we determine 1-maximal nearly perfect sets in the n-fold Cartesian product of graphs and in the n-fold strong product of graphs.
Źródło:
Opuscula Mathematica; 2007, 27, 1; 83-88
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Note on the split domination number of the Cartesian product of paths
Autorzy:
Zwierzchowski, Maciej
Powiązania:
https://bibliotekanauki.pl/articles/744304.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
split domination number
Cartesian product of graphs
Opis:
In this note the split domination number of the Cartesian product of two paths is considered. Our results are related to [2] where the domination number of Pₘ ☐ Pₙ was studied. The split domination number of P₂ ☐ Pₙ is calculated, and we give good estimates for the split domination number of Pₘ ☐ Pₙ expressed in terms of its domination number.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 79-84
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Autorzy:
Azarija, Jernej
Powiązania:
https://bibliotekanauki.pl/articles/30098147.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cartesian product graphs
spanning trees
number of spanning trees
inequality
Opis:
Let $ G_1 $ and $ G_2 $ be simple graphs and let $ n_1 = |V (G_1)| $, $ m_1 = |E(G_1)| $ , $ n_2 = |V (G_2)|$ and $ m_2 = |E(G_2)|$. In this paper we derive sharp upper and lower bounds for the number of spanning trees $ \tau $ in the Cartesian product $ G_1 \square G_2 $ of $ G_1 $ and $ G_2 $. We show that: $$ \tau (G_1 \square G_2 ) \geq \frac{2(n_1-1)(n_2-1)}{n_1 n_2} (\tau (G_1) n_1 )^\frac{n_2+1}{2} (\tau(G_2)n_2)^\frac{n_1+1}{2} $$ and $$ \tau(G_1 \square G_2 ) \leq \tau (G_1) \tau (G_2) \left[ \frac{2m_1}{n_1-1} + \frac{2m_2}{n_2-1} \right]^{(n_1 - 1)(n_2 -1)} . $$ We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in $ K_{n_1} \square K_{n_2} $ which turns out to be $ n_1^{n_1-2} n_2^{n_2-2} (n_1 + n_2 )^{(n_1-1)(n_2-1)} $.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 785-790
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Path-Pairability in the Cartesian Product of Graphs
Autorzy:
Mészáros, Gábor
Powiązania:
https://bibliotekanauki.pl/articles/31340793.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
path-pairable graphs
Cartesian product of graphs
Opis:
We study the inheritance of path-pairability in the Cartesian product of graphs and prove additive and multiplicative inheritance patterns of path-pairability, depending on the number of vertices in the Cartesian product. We present path-pairable graph families that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 743-758
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the rainbow connection of Cartesian products and their subgraphs
Autorzy:
Klavžar, Sandi
Mekiš, Gašper
Powiązania:
https://bibliotekanauki.pl/articles/743307.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow connection
strong rainbow connection
Cartesian product of graphs
isometric subgraph
hypercube
Opis:
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called Θ-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 783-793
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the total restrained domination number of direct products of graphs
Autorzy:
Shiu, Wai
Chen, Hong-Yu
Chen, Xue-Gang
Sun, Pak
Powiązania:
https://bibliotekanauki.pl/articles/743278.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination number
total restrained domination number
direct product of graphs
Opis:
Let G = (V,E) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V∖S is adjacent to a vertex in S as well as to another vertex in V∖S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by $γ_r^t(G)$, is the smallest cardinality of a total restrained dominating set of G. We determine lower and upper bounds on the total restrained domination number of the direct product of two graphs. Also, we show that these bounds are sharp by presenting some infinite families of graphs that attain these bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 629-641
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 21

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies