Good upper bounds for the total rainbow connection of graphs

الأصل · EN

A total-colored graph is a graph G such that both all edges and all vertices of G are colored. A path in a total-colored graph G is a total rainbow path if its edges and internal vertices have distinct colors. A total-colored graph G is total-rainbow connected if any two vertices of G are connected by a total rainbow path of G. The total rainbow connection number of G, denoted by trc(G), is defined as the smallest number of colors that are needed to make G total-rainbow connected. These concepts were introduced by Liu et al. Notice that for a connected graph G, 2diam(G)-1≤ trc(G)≤ 2n-3, where diam(G) denotes the diameter of G and n is the order of G. In this paper we show, for a connected graph G of order n with minimum degree δ, that trc(G)≤6n/(δ+1)+28 for δ≥√n-2-1 and n≥ 291, while trc(G)≤7n/(δ+1)+32 for 16≤δ≤√n-2-2 and trc(G)≤7n/(δ+1)+4C(δ)+12 for 6≤δ≤15, where C(δ)=e3(δ³+2δ²+3)-3(3-1)/δ-3-2. This implies that when δ is in linear with n, then the total rainbow number trc(G) is a constant. We also show that trc(G)≤ 7n/4-3 for δ=3, trc(G)≤8n/5-13/5 for δ=4 and trc(G)≤3n/2-3 for δ=5. Furthermore, an example shows that our bound can be seen tight up to additive factors when δ≥√n-2-1.