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ę "connection," wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 23
Tytuł:
Proper Rainbow Connection Number of Graphs
Autorzy:
Doan, Trung Duy
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/32222687.pdf
Data publikacji:
2021-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-colouring
rainbow connection number
proper rainbow connection number
Opis:
A path in an edge-coloured graph is called a rainbow path if its edges receive pairwise distinct colours. An edge-coloured graph is said to be rainbow connected if any two distinct vertices of the graph are connected by a rainbow path. The minimum k for which there exists such an edge-colouring is the rainbow connection number rc(G) of G. Recently, Bau et al. [Rainbow connectivity in some Cayley graphs, Australas. J. Combin. 71 (2018) 381–393] introduced this concept with the additional requirement that the edge-colouring must be proper. The proper rainbow connection number of G, denoted by prc(G), is the minimum number of colours needed in order to make it properly rainbow connected. Obviously, prc(G) ≥ max{rc(G), χ′(G)}. In this paper we first prove an improved upper bound prc(G) ≤ n for every connected graph G of order n ≥ 3. Next we show that the difference prc(G) – max{rc(G), χ′(G)} can be arbitrarily large. Finally, we present several sufficient conditions for graph classes satisfying prc(G) = χ′(G).
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 809-826
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ł:
The Vertex-Rainbow Connection Number of Some Graph Operations
Autorzy:
Li, Hengzhe
Ma, Yingbin
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/32083892.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow connection number
vertex-rainbow connection number
Cartesian product
lexicographic product
line graph
Opis:
A path in an edge-colored (respectively vertex-colored) graph G is rainbow (respectively vertex-rainbow) if no two edges (respectively internal vertices) of the path are colored the same. An edge-colored (respectively vertex-colored) graph G is rainbow connected (respectively vertex-rainbow connected) if every two distinct vertices are connected by a rainbow (respectively vertex-rainbow) path. The rainbow connection number rc(G) (respectively vertex-rainbow connection number rvc(G)) of G is the smallest number of colors that are needed in order to make G rainbow connected (respectively vertex-rainbow connected). In this paper, we show that for a connected graph G and any edge e = xy ∈ E(G), rvc(G) ≤ rvc(G − e) ≤ rvc(G) + dG−e(x, y) − 1 if G − e is connected. For any two connected, non-trivial graphs G and H, rad(G□H)−1 ≤ rvc(G□H) ≤ 2rad(G□H), where G□H is the Cartesian product of G and H. For any two non-trivial graphs G and H such that G is connected, rvc(G ◦ H) = 1 if diam(G ◦ H) ≤ 2, rad(G) − 1 ≤ rvc(G ◦ H) ≤ 2rad(G) if diam(G) > 2, where G ◦ H is the lexicographic product of G and H. For the line graph L(G) of a graph G we show that rvc(L(G)) ≤ rc(G), which is the first known nontrivial inequality between the rainbow connection number and vertex-rainbow connection number. Moreover, the bounds reported are tight or tight up to additive constants.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 513-530
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hardness Results for Total Rainbow Connection of Graphs
Autorzy:
Chen, Lily
Huo, Bofeng
Ma, Yingbin
Powiązania:
https://bibliotekanauki.pl/articles/31340946.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total rainbow connection
computational complexity
Opis:
A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring of a graph G makes it total rainbow connected is NP-Complete. We also prove that given a graph G, deciding whether trc(G) = 3 is NP-Complete.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 355-362
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with rainbow connection number two
Autorzy:
Kemnitz, Arnfried
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/743883.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge colouring
rainbow colouring
rainbow connection
Opis:
An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) = 2 for every connected graph G of order n and size m, where $\binom{n-1}{2} + 1 ≤ m ≤ \binom{n}{2} - 1$. We also characterize graphs with rainbow connection number two and large clique number.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 313-320
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Distance-Local Rainbow Connection Number
Autorzy:
Septyanto, Fendy
Sugeng, Kiki A.
Powiązania:
https://bibliotekanauki.pl/articles/32222664.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow connection
chromatic number
line graph
Opis:
Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any two vertices with distance at most d can be connected by a rainbow path (respectively, rainbow geodesic). This generalizes rainbow connection numbers, which are the special case d = diam(G). We discuss some bounds and exact values. Moreover, we also characterize all triples of positive integers d, a, b such that there is a connected graph G with lrcd(G) = a and lsrcd(G) = b.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1027-1039
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Disconnection in Graphs
Autorzy:
Chartrand, Gary
Devereaux, Stephen
Haynes, Teresa W.
Hedetniemi, Stephen T.
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/31342243.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
rainbow connection
rainbow disconnection
Opis:
Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G − R. We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G. It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G. It is also shown that for a nontrivial connected graph G of order n, rd(G) = n−1 if and only if G contains at least two vertices of degree n − 1. The rainbow disconnection numbers of all grids Pm □ Pn are determined. Furthermore, it is shown for integers k and n with 1 ≤ k ≤ n − 1 that the minimum size of a connected graph of order n having rainbow disconnection number k is n + k − 2. Other results and a conjecture are also presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1007-1021
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hamiltonian Normal Cayley Graphs
Autorzy:
Montellano-Ballesteros, Juan José
Arguello, Anahy Santiago
Powiązania:
https://bibliotekanauki.pl/articles/31343293.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cayley graph
hamiltonian cycle
normal connection set
Opis:
A variant of the Lovász Conjecture on hamiltonian paths states that every finite connected Cayley graph contains a hamiltonian cycle. Given a finite group G and a connection set S, the Cayley graph Cay(G, S) will be called normal if for every g ∈ G we have that g−1Sg = S. In this paper we present some conditions on the connection set of a normal Cayley graph which imply the existence of a hamiltonian cycle in the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 731-740
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Radio Connection Number of Graphs
Autorzy:
Marinescu-Ghemeci, Ruxandra
Powiązania:
https://bibliotekanauki.pl/articles/31343294.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
radio connection number
radio coloring
L (2, 1)-connection number
L (2, 1)-connectivity
L (2, 1)-labeling
Opis:
Given a graph G and a vertex coloring c, G is called l-radio connected if between any two distinct vertices u and v there is a path such that coloring c restricted to that path is an l-radio coloring. The smallest number of colors needed to make G l-radio connected is called the l-radio connection number of G. In this paper we introduce these notions and initiate the study of connectivity through radio colored paths, providing results on the 2-radio connection number, also called L(2, 1)-connection number: lower and upper bounds, existence problems, exact values for known classes of graphs and graph operations.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 705-730
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Connection Number of Dense Graphs
Autorzy:
Li, Xueliang
Liu, Mengmeng
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/30146190.pdf
Data publikacji:
2013-07-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-colored graph
rainbow coloring
rainbow connection number
Opis:
An edge-colored graph $G$ is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we show that $rc(G) \leq 3$ if \( |E(G)| \geq \binom{n-2}{2} + 2 \), and $ rc(G) \leq 4 $ if \( |E(G)| \geq \binom{n-3}{2} + 3 \). These bounds are sharp.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 3; 603-611
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Proper Connection Of Direct Products
Autorzy:
Hammack, Richard H.
Taylor, Dewey T.
Powiązania:
https://bibliotekanauki.pl/articles/31341584.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
direct product of graphs
proper connection of graphs
Opis:
The proper connection number of a graph is the least integer k for which the graph has an edge coloring with k colors, with the property that any two vertices are joined by a properly colored path. We prove that given two connected non-bipartite graphs, one of which is (vertex) 2-connected, the proper connection number of their direct product is 2.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 1005-1013
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Connection In Sparse Graphs
Autorzy:
Kemnitz, Arnfried
Przybyło, Jakub
Schiermeyer, Ingo
Woźniak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/30146690.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow-connected graph
rainbow colouring
rainbow connection number
Opis:
An edge-coloured connected graph $G = (V,E)$ is called rainbow-connected if each pair of distinct vertices of $G$ is connected by a path whose edges have distinct colours. The rainbow connection number of $G$, denoted by $ \text{rc}(G)$, is the minimum number of colours such that $G$ is rainbow-connected. In this paper we prove that $ \text{rc}(G) \le k $ if $ |V (G)| = n $ and \( |E(G)| \ge \binom{n-k+1}{2} + k -1 \) for all integers $n$ and $k$ with $n − 6 \le k \le n − 3 $. We also show that this bound is tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 181-192
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Connection Number of Graphs with Diameter 3
Autorzy:
Li, Hengzhe
Li, Xueliang
Sun, Yuefang
Powiązania:
https://bibliotekanauki.pl/articles/31342160.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
rainbow path
rainbow connection number
diameter
Opis:
A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G is connected by a rainbow path. Let f(d) denote the minimum number such that rc(G) ≤ f(d) for each bridgeless graph G with diameter d. In this paper, we shall show that 7 ≤ f(3) ≤ 9.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 141-154
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertex rainbow colorings of graphs
Autorzy:
Fujie-Okamoto, Futaba
Kolasinski, Kyle
Lin, Jianwei
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/743667.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow path
vertex rainbow coloring
vertex rainbow connection number
Opis:
In a properly vertex-colored graph G, a path P is a rainbow path if no two vertices of P have the same color, except possibly the two end-vertices of P. If every two vertices of G are connected by a rainbow path, then G is vertex rainbow-connected. A proper vertex coloring of a connected graph G that results in a vertex rainbow-connected graph is a vertex rainbow coloring of G. The minimum number of colors needed in a vertex rainbow coloring of G is the vertex rainbow connection number vrc(G) of G. Thus if G is a connected graph of order n ≥ 2, then 2 ≤ vrc(G) ≤ n. We present characterizations of all connected graphs G of order n for which vrc(G) ∈ {2,n-1,n} and study the relationship between vrc(G) and the chromatic number χ(G) of G. For a connected graph G of order n and size m, the number m-n+1 is the cycle rank of G. Vertex rainbow connection numbers are determined for all connected graphs of cycle rank 0 or 1 and these numbers are investigated for connected graphs of cycle rank 2.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 1; 63-80
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Vertex-Connection and Forbidden Subgraphs
Autorzy:
Li, Wenjing
Li, Xueliang
Zhang, Jingshu
Powiązania:
https://bibliotekanauki.pl/articles/31342433.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex-rainbow path
rainbow vertex-connection
forbidden sub-graphs
Opis:
A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ {1, 2}, for which there is a constant kℱ such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + kℱ, where diam(G) is the diameter of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 143-154
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 23

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