Li, Xueliang; Schiermeyer, Ingo; Yang, Kang; Zhao, Yan Graphs with 3-rainbow index \(n-1\) and \(n-2\). (English) Zbl 1307.05051 Discuss. Math., Graph Theory 35, No. 1, 105-120 (2015). 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. Cited in 6 Documents MSC: 05C05 Trees 05C15 Coloring of graphs and hypergraphs 05C75 Structural characterization of families of graphs Keywords:rainbow \(S\)-tree; \(k\)-rainbow index Citations:Zbl 1205.05085 PDFBibTeX XMLCite \textit{X. Li} et al., Discuss. Math., Graph Theory 35, No. 1, 105--120 (2015; Zbl 1307.05051) 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.