Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
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. I...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2018-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2056 |
| _version_ | 1797757772906889216 |
|---|---|
| author | Sun Yuefang Jin Zemin Tu Jianhua |
| author_facet | Sun Yuefang Jin Zemin Tu Jianhua |
| author_sort | Sun Yuefang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T18:19:23Z |
| format | Article |
| id | doaj.art-931a99d6f3ba41b19bbbefc43df23862 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:23Z |
| publishDate | 2018-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-931a99d6f3ba41b19bbbefc43df238622023-08-02T08:59:12ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922018-11-013841023103610.7151/dmgt.2056dmgt.2056Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection NumberSun Yuefang0Jin Zemin1Tu Jianhua2Department of Mathematics, Shaoxing University, Zhejiang312000, P.R. ChinaDepartment of Mathematics, Zhejiang Normal University, Zhejiang321004, P.R. ChinaSchool of Science, Beijing University of Chemical Technology, Beijing100029, P.R. ChinaA 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.https://doi.org/10.7151/dmgt.2056rainbow total-coloringrainbow total-connection numbercomplementary grapherdős-gallai type problem05c1505c3505c75 |
| spellingShingle | Sun Yuefang Jin Zemin Tu Jianhua Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number Discussiones Mathematicae Graph Theory rainbow total-coloring rainbow total-connection number complementary graph erdős-gallai type problem 05c15 05c35 05c75 |
| title | Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number |
| title_full | Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number |
| title_fullStr | Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number |
| title_full_unstemmed | Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number |
| title_short | Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number |
| title_sort | rainbow total coloring of complementary graphs and erdos gallai type problem for the rainbow total connection number |
| topic | rainbow total-coloring rainbow total-connection number complementary graph erdős-gallai type problem 05c15 05c35 05c75 |
| url | https://doi.org/10.7151/dmgt.2056 |
| work_keys_str_mv | AT sunyuefang rainbowtotalcoloringofcomplementarygraphsanderdosgallaitypeproblemfortherainbowtotalconnectionnumber AT jinzemin rainbowtotalcoloringofcomplementarygraphsanderdosgallaitypeproblemfortherainbowtotalconnectionnumber AT tujianhua rainbowtotalcoloringofcomplementarygraphsanderdosgallaitypeproblemfortherainbowtotalconnectionnumber |