Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number

Abstract

A total-colored graph G is rainbow total-connected if any two vertices of G are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum number of colors needed to make G rainbow total-connected. In this paper, we prove that rtc(G) can be bounded by a constant 7 if the following three cases are excluded: diam(Ḡ) = 2, diam(Ḡ) = 3, Ḡ contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erdős-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function f(n, k), where f(n, k) is the minimum value satisfying the following property: if |E(G)| ≥ f(n, k), then rtc(G) ≤ k.

Keywords

• rainbow total-coloring
• rainbow total-connection number
• complementary graph
• erdős-gallai type problem
• 05c15
• 05c35
• 05c75