2015/01/08 by Hui Jiang, Xueliang Li, Jiang, Hui +3
Computer Science · Mathematics · #05C15 #05C40 #05C69 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1501.01806
openalex publication_date 2015/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(δ)=e(3log(δ3+2δ2+3)-3(log3-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.