- Tytuł:
- Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
- Autorzy:
-
Sun, Yuefang
Jin, Zemin
Tu, Jianhua - Powiązania:
- https://bibliotekanauki.pl/articles/31342242.pdf
- Data publikacji:
- 2018-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Rainbow total-coloring
rainbow total-connection number
complementary graph
Erdős-Gallai type problem - Opis:
- 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( \overline{G} ) = 2 $, $ diam( \overline{G} ) = 3 $, $ \overline{G} $ 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)| \ge f(n, k) $, then $ rtc(G) \le k $.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1023-1036
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł