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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 16
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ł:
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ł:
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ł:
On the Rainbow Vertex-Connection
Autorzy:
Li, Xueliang
Shi, Yongtang
Powiązania:
https://bibliotekanauki.pl/articles/30146636.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow vertex-connection
vertex coloring
minimum degree
2-step dominating set
Opis:
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It was proved that if $G$ is a graph of order $n$ with minimum degree $ \delta $, then $ rvc(G) < 11n//\delta$. In this paper, we show that $rvc(G) \le 3n//(δ+1)+5$ for $ \delta \ge \sqrt{n-1} -1 $ and $ n \le 290 $, while $ rvc(G) \le 4n//(δ + 1) + 5 $ for $ 16 \le \delta \le \sqrt{n-1}-2 $ and $ rvc(G) \le 4n//(\delta + 1) + C(\delta) $ for $6 \le \delta \le 15$, where $ C(\delta) = e^\frac{ 3 \log (\delta^3 + 2 \delta^2 +3)-3(\log 3 - 1)}{\delta - 3} - 2$. We also prove that $ rvc(G) \le 3n//4 − 2 $ for $ \delta = 3$, $ rvc(G) \le 3n//5 − 8//5$ for $\delta = 4$ and $rvc(G) \le n//2 − 2$ for $\delta = 5$. Moreover, an example constructed by Caro et al. shows that when $ \delta \ge \sqrt{n-1} - 1 $ and $ \delta = 3, 4, 5 $, our bounds are seen to be tight up to additive constants.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 307-313
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 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ł:
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ł:
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ł:
Generalized Rainbow Connection of Graphs and their Complements
Autorzy:
Li, Xueliang
Magnant, Colton
Wei, Meiqin
Zhu, Xiaoyu
Powiązania:
https://bibliotekanauki.pl/articles/31342420.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
ℓ-rainbow path
( k, ℓ)-rainbow connected
( k, ℓ)-rainbow connection number
Opis:
Let $G$ be an edge-colored connected graph. A path $P$ in $G$ is called $ \mathcal{l} $-rainbow if each subpath of length at most $ \mathcal{l} + 1 $ is rainbow. The graph $G$ is called $(k, \mathcal{l} )$-rainbow connected if there is an edge-coloring such that every pair of distinct vertices of $G$ is connected by $k$ pairwise internally vertex-disjoint $ \mathcal{l} $-rainbow paths in $G$. The minimum number of colors needed to make $G$ $(k, \mathcal{l})$-rainbow connected is called the $ (k, \mathcal{l} )$-rainbow connection number of $G$ and denoted by $ rc_{ k,\mathcal{l} } (G) $. In this paper, we first focus on the (1, 2)-rainbow connection number of $G$ depending on some constraints of $ \overline{G} $. Then, we characterize the graphs of order $n$ with (1, 2)-rainbow connection number $ n − 1 $ or $ n − 2 $. Using this result, we investigate the Nordhaus-Gaddum-Type problem of (1, 2)-rainbow connection number and prove that $ rc_{1,2}(G) + rc_{1,2}( \overlina{G} ) \le n + 2 $ for connected graphs $ G $ and $ \overline{G} $. The equality holds if and only if $G$ or $ \overline{G} $ is isomorphic to a double star.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 371-384
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ł:
Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
Autorzy:
Sun, Yuefang
Jin, Zemin
Tu, Jianhua
Powiązania:
https://bibliotekanauki.pl/articles/31342242.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Rainbow total-coloring
rainbow total-connection number
complementary graph
Erdős-Gallai type problem
Opis:
A total-colored graph $G$ is rainbow total-connected if any two vertices of $G$ are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by $ rtc(G) $, of a graph $G$ is the minimum number of colors needed to make $G$ rainbow total-connected. In this paper, we prove that $ rtc(G) $ can be bounded by a constant 7 if the following three cases are excluded: $ diam( \overline{G} ) = 2 $, $ diam( \overline{G} ) = 3 $, $ \overline{G} $ contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erdős-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function $ f(n, k) $, where $ f(n, k) $ is the minimum value satisfying the following property: if $ |E(G)| \ge f(n, k) $, then $ rtc(G) \le k $.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1023-1036
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ł
Tytuł:
On Proper (Strong) Rainbow Connection of Graphs
Autorzy:
Jiang, Hui
Li, Wenjing
Li, Xueliang
Magnant, Colton
Powiązania:
https://bibliotekanauki.pl/articles/32083886.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
proper (strong) rainbow connection number
Cartesian product
chromatic index
Opis:
A path in an edge-colored graph $G$ is called a rainbow path if no two edges on the path have the same color. The graph $G$ is called rainbow connected if between every pair of distinct vertices of $G$, there is a rainbow path. Recently, Johnson et al. considered this concept with the additional requirement that the coloring of $G$ is proper. The proper rainbow connection number of $G$, denoted by $prc(G)$, is the minimum number of colors needed to properly color the edges of $G$ so that $G$ is rainbow connected. Similarly, the proper strong rainbow connection number of $G$, denoted by $psrc(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that for any two distinct vertices of $G$, there is a rainbow geodesic (shortest path) connecting them. In this paper, we characterize those graphs with proper rainbow connection numbers equal to the size or within 1 of the size. Moreover, we completely solve a question proposed by Johnson et al. by proving that if \(G = K_{p1} \Box \dots \Box K_{pn}\), where $n≥ 1$, and $p_1, . . ., p_n>1$ are integers, then $prc(G) = psrc(G) = χ^′(G)$, where $χ^′(G)$ denotes the chromatic index of $G$. Finally, we investigate some suffcient conditions for a graph $G$ to satisfy $prc(G) = rc(G)$, and make some slightly positive progress by using a relation between $rc(G)$ and the girth of the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 469-479
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
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ł:
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ł
Wyświetlanie 1-15 z 16

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