Upper bounds for the total rainbow connection of graphs

A total-colored graph is a graph such that both all edges and all vertices of the graph are colored. A path in a total-colored graph is a total rainbow path if its edges and internal vertices have distinct colors. A total-colored graph is total-rainbow connected if any two vertices of the graph are connected by a total-rainbow path of the graph. For a connected graph $$G$$ G , the total rainbow connection number of $$G$$ G , denoted by $$trc(G)$$ t r c ( G ) , is defined as the smallest number of colors that are needed to make $$G$$ G total-rainbow connected. These concepts were introduced by Liu et al. Notice that for a connected graph $$G$$ G , $$2diam(G)-1\le trc(G)\le 2n-3$$ 2 d i a m ( G ) - 1 ≤ t r c ( G ) ≤ 2 n - 3 , where $$diam(G)$$ d i a m ( G ) denotes the diameter of $$G$$ G and $$n$$ n is the order of $$G$$ G . In this paper we show, for a connected graph $$G$$ G of order $$n$$ n with minimum degree $$\delta $$ δ , that $$trc(G)\le 6n/{(\delta +1)}+28$$ t r c ( G ) ≤ 6 n / ( δ + 1 ) + 28 for $$\delta \ge \sqrt{n-2}-1$$ δ ≥ n - 2 - 1 and $$n\ge 291$$ n ≥ 291 , while $$trc(G)\le 7n/{(\delta +1)}+32$$ t r c ( G ) ≤ 7 n / ( δ + 1 ) + 32 for $$16\le \delta \le \sqrt{n-2}-2$$ 16 ≤ δ ≤ n - 2 - 2 and $$trc(G)\le 7n/{(\delta +1)}+4C(\delta )+12$$ t r c ( G ) ≤ 7 n / ( δ + 1 ) + 4 C ( δ ) + 12 for $$6\le \delta \le 15$$ 6 ≤ δ ≤ 15 , where $$C(\delta )=e^{\frac{3\log ({\delta }^3+2{\delta }^2+3)-3(\log 3-1)}{\delta -3}}-2$$ C ( δ ) = e 3 log ( δ 3 + 2 δ 2 + 3 ) - 3 ( log 3 - 1 ) δ - 3 - 2 . Thus, when $$\delta $$ δ is in linear with $$n$$ n , the total rainbow number $$trc(G)$$ t r c ( G ) is a constant. We also show that $$trc(G)\le 7n/4-3$$ t r c ( G ) ≤ 7 n / 4 - 3 for $$\delta =3$$ δ = 3 , $$trc(G)\le 8n/5-13/5$$ t r c ( G ) ≤ 8 n / 5 - 13 / 5 for $$\delta =4$$ δ = 4 and $$trc(G)\le 3n/2-3$$ t r c ( G ) ≤ 3 n / 2 - 3 for $$\delta =5$$ δ = 5 . Furthermore, an example from Caro et al. shows that our bound can be seen tight up to additive factors when $$\delta \ge \sqrt{n-2}-1$$ δ ≥ n - 2 - 1 .