Graphs with 4-Rainbow Index 3 and n − 1

Xueliang Li; Ingo Schiermeyer; Kang Yang; Yan Zhao

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 387-398
  • ISSN: 2083-5892

Abstract

top
Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree that connects 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 every set S of k vertices of V (G) is called the k-rainbow index of G, denoted by rxk(G). Notice that a lower bound and an upper bound of the k-rainbow index of a graph with order n is k − 1 and n − 1, respectively. Chartrand et al. got that the k-rainbow index of a tree with order n is n − 1 and the k-rainbow index of a unicyclic graph with order n is n − 1 or n − 2. Li and Sun raised the open problem of characterizing the graphs of order n with rxk(G) = n − 1 for k ≥ 3. In early papers we characterized the graphs of order n with 3-rainbow index 2 and n − 1. In this paper, we focus on k = 4, and characterize the graphs of order n with 4-rainbow index 3 and n − 1, respectively.

How to cite

top

Xueliang Li, et al. "Graphs with 4-Rainbow Index 3 and n − 1." Discussiones Mathematicae Graph Theory 35.2 (2015): 387-398. <http://eudml.org/doc/271092>.

@article{XueliangLi2015,
abstract = {Let G be a nontrivial connected graph with an edge-coloring c : E(G) → \{1, 2, . . . , q\}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree that connects 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 every set S of k vertices of V (G) is called the k-rainbow index of G, denoted by rxk(G). Notice that a lower bound and an upper bound of the k-rainbow index of a graph with order n is k − 1 and n − 1, respectively. Chartrand et al. got that the k-rainbow index of a tree with order n is n − 1 and the k-rainbow index of a unicyclic graph with order n is n − 1 or n − 2. Li and Sun raised the open problem of characterizing the graphs of order n with rxk(G) = n − 1 for k ≥ 3. In early papers we characterized the graphs of order n with 3-rainbow index 2 and n − 1. In this paper, we focus on k = 4, and characterize the graphs of order n with 4-rainbow index 3 and n − 1, 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 = {2},
pages = {387-398},
title = {Graphs with 4-Rainbow Index 3 and n − 1},
url = {http://eudml.org/doc/271092},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Xueliang Li
AU - Ingo Schiermeyer
AU - Kang Yang
AU - Yan Zhao
TI - Graphs with 4-Rainbow Index 3 and n − 1
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 387
EP - 398
AB - Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree that connects 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 every set S of k vertices of V (G) is called the k-rainbow index of G, denoted by rxk(G). Notice that a lower bound and an upper bound of the k-rainbow index of a graph with order n is k − 1 and n − 1, respectively. Chartrand et al. got that the k-rainbow index of a tree with order n is n − 1 and the k-rainbow index of a unicyclic graph with order n is n − 1 or n − 2. Li and Sun raised the open problem of characterizing the graphs of order n with rxk(G) = n − 1 for k ≥ 3. In early papers we characterized the graphs of order n with 3-rainbow index 2 and n − 1. In this paper, we focus on k = 4, and characterize the graphs of order n with 4-rainbow index 3 and n − 1, respectively.
LA - eng
KW - rainbow S-tree; k-rainbow index; rainbow -tree; -rainbow index
UR - http://eudml.org/doc/271092
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008). 
  2. [2] Q. Cai, X. Li and J. Song, Solutions to conjectures on the (k, ℓ)-rainbow index of complete graphs, Networks 62 (2013) 220-224. doi:10.1002/net.21513[Crossref][WoS] 
  3. [3] Y. Caro, A. Lev, Y. Roditty, Zs. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) R57. Zbl1181.05037
  4. [4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
  5. [5] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75-81. doi:10.1002/net.20296[WoS][Crossref] Zbl1205.05124
  6. [6] G. Chartrand, S.F. Kappor, L. Lesniak and D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq 2 (1984) 1-6. 
  7. [7] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360-367. doi:10.1002/net.20399[Crossref][WoS] Zbl1205.05085
  8. [8] 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[WoS][Crossref] Zbl1307.05066
  9. [9] P. Erdős and A. Gyárfás, A variant of the classical Ramsey problem, Combinatorica 17 (1997) 459-467. doi:10.1007/BF01195000[Crossref] Zbl0910.05034
  10. [10] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs in Math., Springer, New York, 2012). Zbl1250.05066
  11. [11] 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[Crossref][WoS] Zbl1258.05058
  12. [12] X. Li, I. Schiermeyer, K. Yang and Y. Zhao, Graphs with 3-rainbow index n−1 and n − 2, Discuss. Math. Graph Theory 35 (2015) 105-120. doi:10.7151/dmgt.1783 [Crossref][WoS] Zbl1307.05051

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.