Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
| Autor: | Zemin Jin, Yuefang Sun, Jianhua Tu |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Applied Mathematics
010102 general mathematics Total coloring Rainbow 0102 computer and information sciences Type (model theory) 01 natural sciences complementary graph Combinatorics rainbow total-coloring 010201 computation theory & mathematics rainbow total-connection number 05c15 QA1-939 Discrete Mathematics and Combinatorics Connection number erdős-gallai type problem 0101 mathematics 05c35 Mathematics 05c75 |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 38, Iss 4, Pp 1023-1036 (2018) |
| ISSN: | 2083-5892 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|