Graphs with small total rainbow connection number

Abstract

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 \mathrm{trc}(G)=\mathrm{3}\hspace{0.17em}\mathrm{if}\left(\begin{array}{l}n-\mathrm{1}\\ \mathrm{2}\end{array}\right)+\mathrm{1}\le \left|E(G)\right|\le \left(\begin{array}{l}n\\ \mathrm{2}\end{array}\right)-\mathrm{1}, and \mathrm{trc}(G)=\mathrm{6}\hspace{0.17em}\mathrm{if}\left(\begin{array}{l}n-\mathrm{2}\\ \mathrm{2}\end{array}\right)+\mathrm{2}\le . Next, we investigate the total rainbow connection numbers of graphs G with \left|V(G)\right|=n, diam(G)\ge \mathrm{2}, and clique number \omega (G)=n-s\hspace{0.17em}\mathrm{for}\hspace{0.17em}\mathrm{1}\hspace{0.17em}\le s\le \hspace{0.17em}\mathrm{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.

Key words： Total-coloring; total rainbow path; total rainbow connected; total rainbow connection number; clique number

References

1 BondyJ A, MurtyU S R. Graph Theory. Berlin: Springer, 2008

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

4 HuangX, LiX, ShiY, YueJ, ZhaoY. Rainbow connections for outerplanar graphs with diameter 2 and 3. Appl Math Comput, 2014, 242: 277–280

5 KemnitzA, SchiermeyerI. Graphs with rainbow connection number two. Discuss Math Graph Theory, 2011, 31(2): 313–320

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

7 LiS, LiX, ShiY. Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs. Appl Math Comput, 2015, 258: 155–161

8 LiX, LiuM, SchiermeyerI. Rainbow connection number of dense graphs. Discuss Math Graph Theory, 2013, 33(3): 603–611

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

11 LiX, ShiY, SunY. Rainbow connections of graphs: A survey. Graphs Combin, 2013, 29(1): 1–38

12 LiX, SunY.Rainbow Connections of Graphs. New York: Springer, 2012

13 LiuH, MestreÂ, SousaT. Total rainbow k-connection in graphs. Discrete Appl Math, 2014, 174: 92–101

14 MaoY, ShiY. The complexity of determining the vertex-rainbow index of graphs. Discrete Math Algorithms Appl, 2015, 7(4): 1550047

15 UchizawaK, AokiT, ItoT, SuzukiA, ZhouX. On the rainbow connectivity of graphs: Complexity and FPT algorithms. Algorithmica, 2013, 67(2): 161–179