On rainbow total-coloring of a graph

A path PP connecting two vertices uu and vv in a total-colored graph GG is called a rainbow total-path between uu and vv if all elements in V(P)∪E(P)V(P)∪E(P), except for uu and vv, are assigned distinct colors. The total-colored graph GG is rainbow total-connected if it has a rainbow total-path between every two vertices. The rainbow total-connection number, denoted by rtc(G)rtc(G), of a graph GG is the minimum colors such that GG is rainbow total-connected. It was shown that rtc(G)≤m(G)+n′(G)rtc(G)≤m(G)+n′(G), and the equality holds if and only if GG is a tree, where n′(G)n′(G) is the number of inner vertices of GG. In this paper, we show that rtc(G)≠m(G)+n′(G)−1,m(G)+n′(G)−2rtc(G)≠m(G)+n′(G)−1,m(G)+n′(G)−2 and characterize the graphs with rtc(G)=m(G)+n′(G)−3rtc(G)=m(G)+n′(G)−3. With this result, the following sharp upper bound holds: for a connected graph GG, if GG is not a tree, then rtc(G)≤m(G)+n′(G)−3rtc(G)≤m(G)+n′(G)−3; moreover, the equality holds if and only if GG belongs to five graph classes. We also investigate the Nordhaus–Gaddum-type lower bounds for the rainbow total-connection number of a graph and derive that if GG is a connected graph of order n≥8n≥8, then rtc(G)+rtc(G¯)≥6 and rtc(G)rtc(G¯)≥9. An example is given to show that both of these bounds are sharp.