Please wait a minute...

Frontiers of Mathematics in China

Front. Math. China    2017, Vol. 12 Issue (4) : 921-936     DOI: 10.1007/s11464-017-0651-2
Graphs with small total rainbow connection number
Yingbin MA1(), Lily CHEN2, Hengzhe LI1
1. College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China
2. School of Mathematics Science, Huaqiao University, Quanzhou 362021, China
Download: PDF(169 KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that trc(G)=3?if(n12)+1|E(G)|(n2)1, and trc(G)=6?if(n22)+2. Next, we investigate the total rainbow connection numbers of graphs G with |V(G)|=n, diam(G)2, and clique number ω(G)=ns?for?1?s?3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31(2): 313–320] is not completely correct, and we provide a complete result for this theorem.

Keywords Total-coloring      total rainbow path      total rainbow connected      total rainbow connection number      clique number     
Corresponding Authors: Yingbin MA   
Issue Date: 06 July 2017
 Cite this article:   
Yingbin MA,Lily CHEN,Hengzhe LI. Graphs with small total rainbow connection number[J]. Front. Math. China, 2017, 12(4): 921-936.
E-mail this article
E-mail Alert
Articles by authors
Yingbin MA
Hengzhe LI
1 BondyJ A, MurtyU S R. Graph Theory. Berlin: Springer, 2008
doi: 10.1007/978-1-84628-970-5
2 ChartrandG, JohnsG L, McKeonK A, ZhangP. Rainbow connection in graphs. Math Bohem, 2008, 133: 85–98
3 HuangX, LiX, ShiY. Rainbow connections for planar graphs and line graphs. Bull Malays Math Sci Soc, 2015, 38(3): 1235–1241
doi: 10.1007/s40840-014-0077-x
4 HuangX, LiX, ShiY, YueJ, ZhaoY. Rainbow connections for outerplanar graphs with diameter 2 and 3. Appl Math Comput, 2014, 242: 277–280
doi: 10.1016/j.amc.2014.05.066
5 KemnitzA, SchiermeyerI. Graphs with rainbow connection number two. Discuss Math Graph Theory, 2011, 31(2): 313–320
doi: 10.7151/dmgt.1547
6 KrivelevichM, YusterR. The rainbow connection of a graph is (at most) reciprocal to its minimum degree.J Graph Theory, 2009, 63(3): 185–191
doi: 10.1002/jgt.20418
7 LiS, LiX, ShiY. Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs. Appl Math Comput, 2015, 258: 155–161
doi: 10.1016/j.amc.2015.02.015
8 LiX, LiuM, SchiermeyerI. Rainbow connection number of dense graphs. Discuss Math Graph Theory, 2013, 33(3): 603–611
doi: 10.7151/dmgt.1692
9 LiX, MaoY, ShiY. The strong rainbow vertex-connection of graphs. Util Math, 2014, 93: 213–223
10 LiX, ShiY. Rainbow connection in 3-connected graphs. Graphs Combin, 2013, 29(5): 1471–1475
doi: 10.1007/s00373-012-1204-9
11 LiX, ShiY, SunY. Rainbow connections of graphs: A survey. Graphs Combin, 2013, 29(1): 1–38
doi: 10.1007/s00373-012-1243-2
12 LiX, SunY.Rainbow Connections of Graphs. New York: Springer, 2012
doi: 10.1007/978-1-4614-3119-0
13 LiuH, MestreÂ, SousaT. Total rainbow k-connection in graphs. Discrete Appl Math, 2014, 174: 92–101
doi: 10.1016/j.dam.2014.04.012
14 MaoY, ShiY. The complexity of determining the vertex-rainbow index of graphs. Discrete Math Algorithms Appl, 2015, 7(4): 1550047
doi: 10.1142/S1793830915500470
Related articles from Frontiers Journals
[1] Baogang XU,Yingli ZHANG. Chromatic number and subtrees of graphs[J]. Front. Math. China, 2017, 12(2): 441-457.
Full text