Graphs with 3-Rainbow Index n − 1 and n − 2

Xueliang Li; Ingo Schiermeyer; Kang Yang; Yan Zhao

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 1, page 105-120
  • ISSN: 2083-5892

Abstract

top
Let G = (V (G),E(G)) be a nontrivial connected graph of order n with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ 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 ⊆ 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 rxk(G), where k is an integer such that 2 ≤ k ≤ n. Chartrand et al. 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.

How to cite

top

Xueliang Li, et al. "Graphs with 3-Rainbow Index n − 1 and n − 2." Discussiones Mathematicae Graph Theory 35.1 (2015): 105-120. <http://eudml.org/doc/271224>.

@article{XueliangLi2015,
abstract = {Let G = (V (G),E(G)) be a nontrivial connected graph of order n with an edge-coloring c : E(G) → \{1, 2, . . . , q\}, q ∈ 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 ⊆ 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 rxk(G), where k is an integer such that 2 ≤ k ≤ n. Chartrand et al. 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.},
author = {Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {rainbow S-tree; k-rainbow index; rainbow -tree; -rainbow index},
language = {eng},
number = {1},
pages = {105-120},
title = {Graphs with 3-Rainbow Index n − 1 and n − 2},
url = {http://eudml.org/doc/271224},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Xueliang Li
AU - Ingo Schiermeyer
AU - Kang Yang
AU - Yan Zhao
TI - Graphs with 3-Rainbow Index n − 1 and n − 2
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 105
EP - 120
AB - Let G = (V (G),E(G)) be a nontrivial connected graph of order n with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ 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 ⊆ 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 rxk(G), where k is an integer such that 2 ≤ k ≤ n. Chartrand et al. 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.
LA - eng
KW - rainbow S-tree; k-rainbow index; rainbow -tree; -rainbow index
UR - http://eudml.org/doc/271224
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008). 
  2. [2] G. Chartrand, G. Johns, K. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
  3. [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[WoS][Crossref] Zbl1205.05085
  4. [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[Crossref] 
  5. [5] Y. Caro, A. Lev, Y. Roditty, Zs. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57. Zbl1181.05037
  6. [6] G. Chartrand, S. Kappor, L. Lesniak and D. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1-6. 
  7. [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[Crossref][WoS] Zbl1205.05124
  8. [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[WoS][Crossref] Zbl1258.05058
  9. [9] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs in Math., Springer, 2012). Zbl1250.05066

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.