×

Graphs with 3-rainbow index \(n-1\) and \(n-2\). (English) Zbl 1307.05051

Summary: Let \(G=(V(G),E(G))\) be a nontrivial connected graph of order \(n\) with an edge-coloring \(c:E(G)\to\{1,2,\dots,q\}\), \(q\in N\), where adjacent edges may be colored the same. A tree \(T\) in \(G\) is a rainbow tree if no two edges of \(T\) receive the same color. For a vertex set \(S \subseteq V(G)\), a tree connecting \(S\) in \(G\) is called an \(S\)-tree. The minimum number of colors that are needed in an edge-coloring of \(G\) such that there is a rainbow \(S\)-tree for each \(k\)-subset \(S\) of \(V(G)\) is called the \(k\)-rainbow index of \(G\), denoted by \(rx_{k}(G)\), where \(k\) is an integer such that \(2\leq k\leq n\). G. Chartrand et al. [Networks 55, No. 4, 360–367 (2010; Zbl 1205.05085)] got that the \(k\)-rainbow index of a tree is \(n-1\) and the \(k\)-rainbow index of a unicyclic graph is \(n-1\) or \(n-2\). So there is an intriguing problem: Characterize graphs with the \(k\)-rainbow index \(n-1\) and \(n-2\). In this paper, we focus on \(k=3\), and characterize the graphs whose 3-rainbow index is \(n-1\) and \(n-2\), respectively.

MSC:

05C05 Trees
05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs

Citations:

Zbl 1205.05085
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008).;
[2] G. Chartrand, G. Johns, K. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98.; · Zbl 1199.05106
[3] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360-367. doi:10.1002/net.20339; · Zbl 1205.05085
[4] L. Chen, X. Li, K. Yang and Y. Zhao, The 3-rainbow index of a graph, Discuss. Math. Graph Theory 35 (2015) 81-94. doi:10.7151/dmgt.1780; · Zbl 1307.05066
[5] Y. Caro, A. Lev, Y. Roditty, Zs. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57.; · Zbl 1181.05037
[6] G. Chartrand, S. Kappor, L. Lesniak and D. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1-6.;
[7] G. Chartrand, G. Johns, K. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75-81. doi:10.1002/net.20296; · Zbl 1205.05124
[8] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1-38. doi:10.1007/s00373-012-1243-2; · Zbl 1258.05058
[9] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs in Math., Springer, 2012).; · Zbl 1250.05066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.