- 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ł