The 3-rainbow index and connected dominating sets

Qingqiong Cai (), Xueliang Li () and Yan Zhao ()
Additional contact information
Qingqiong Cai: Nankai University
Xueliang Li: Nankai University
Yan Zhao: Nankai University

Journal of Combinatorial Optimization, 2016, vol. 31, issue 3, No 14, 1142-1159

Abstract: Abstract A tree in an edge-colored graph is said to be rainbow if no two edges on the tree share the same color. An edge-coloring of $$G$$ G is called a 3-rainbow coloring if for any three vertices in $$G$$ G , there exists a rainbow tree connecting them. The 3-rainbow index $$rx_3(G)$$ r x 3 ( G ) of $$G$$ G is defined as the minimum number of colors that are needed in a 3-rainbow coloring of $$G$$ G . This concept, introduced by Chartrand et al., can be viewed as a generalization of the rainbow connection. In this paper, we study the 3-rainbow index by using connected 3-way dominating sets and 3-dominating sets. We show that for every connected graph $$G$$ G on $$n$$ n vertices with minimum degree at least $$\delta \, (3\le \delta \le 5)$$ δ ( 3 ≤ δ ≤ 5 ) , $$rx_{3}(G)\le \frac{3n}{\delta +1}+4$$ r x 3 ( G ) ≤ 3 n δ + 1 + 4 , and the bound is tight up to an additive constant; whereas for every connected graph $$G$$ G on $$n$$ n vertices with minimum degree at least $$\delta \, (\delta \ge 3)$$ δ ( δ ≥ 3 ) , we get that $$rx_{3}(G)\le \frac{\ln (\delta +1)}{\delta +1}(1+o_{\delta }(1))n+5$$ r x 3 ( G ) ≤ ln ( δ + 1 ) δ + 1 ( 1 + o δ ( 1 ) ) n + 5 . In addition, we obtain some tight upper bounds of the 3-rainbow index for some special graph classes, including threshold graphs, chain graphs and interval graphs.

Keywords: 3-rainbow index; Connected dominating sets; Rainbow paths; 05C15; 05C38; 05C69 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9815-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:3:d:10.1007_s10878-014-9815-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9815-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().