Total rainbow connection numbers of some special graphs. (English) Zbl 1428.05113
Summary: In [Math. Bohem. 133, No. 1, 85–98 (2008; Zbl 1199.05106)], G. Chartrand et al. first introduced the concept of rainbow connection. Since then, the study of rainbow connection has received considerable attention in the literature, and now it becomes an active topic in graph theory. As a natural generalization, K. Uchizawa et al. [Algorithmica 67, No. 2, 161–179 (2013; Zbl 1290.68060)] and H. Liu et al. [Discrete Appl. Math. 174, 92–101 (2014; Zbl 1298.05127)] presented the concept of total rainbow connection, respectively. In this paper, we investigate the total rainbow connection numbers of outerplanar graphs with diameter 2. Applying our result, we improve the main result of X. Huang et al. [Appl. Math. Comput. 242, 277–280 (2014; Zbl 1334.05038)]. Next, we revise the main result of Y. Liu and Z. Wang [“Rainbow connection number of the thorn graph”, Appl. Math. Sci., Ruse 8, No. 128, 6373–6377 (2014; doi:10.12988/ams.2014.48633)] and determine the total rainbow connection numbers of graphs \(G\), where \(G\) are the thorn graph of complete graph \(\text{K}_n^\ast \), the thorn graph of the cycle \(\text{C}_n^\ast \). At last, we study the rainbow 2-connection numbers of some special graphs.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C35 | Extremal problems in graph theory |
| 05C40 | Connectivity |
Keywords:
total rainbow connection number; outerplanar graph; diameter; thorn graph; rainbow 2-connection numberReferences:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001 |
| [2] | Chandran, L. S.; Das, A.; Rajendraprasad, D.; Varma, N. M., Rainbow connection number and connected dominating sets, J. Graph Theory, 71, 206-218 (2012) · Zbl 1248.05098 |
| [3] | Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., Rainbow connection in graphs, Math. Bohem., 133, 85-98 (2008) · Zbl 1199.05106 |
| [4] | Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., The rainbow connectivity of a graph, Networks, 54, 75-81 (2009) · Zbl 1205.05124 |
| [5] | Chen, L.; Huo, B.; Ma, Y., Hardness results for total rainbow connection of graphs, Discuss. Math. Graph Theory, 36, 355-362 (2016) · Zbl 1338.05077 |
| [6] | Diestel, R., Graph Theory (2000), Springer: Springer Berlin · Zbl 0945.05002 |
| [7] | Fujie-Okamoto, F.; Johns, G. L.; Zhang, P., The rainbow connectivities of small cubic graphs, Ars Combin., 105, 129-147 (2012) · Zbl 1274.05166 |
| [8] | Huang, X.; Li, X.; Shi, Y., Rainbow connections for planar graphs and line graphs, Bull. Malays. Math. Sci. Soc., 38, 1235-1241 (2015) · Zbl 1317.05058 |
| [9] | Huang, X.; Li, X.; Shi, Y.; Yue, J.; Zhao, Y., Rainbow connections for outerplanar graphs with diameter 2 and 3, Appl. Math. Comput., 242, 277-280 (2014) · Zbl 1334.05038 |
| [10] | Jiang, H.; Li, X.; Zhang, Y., Upper bounds for the total rainbow connection of graphs, J. Comb. Optim., 32, 260-266 (2016) · Zbl 1347.05068 |
| [11] | Kirlangic, A., The scattering number of thorn graphs, Int. J. Comput. Math., 82, 299-311 (2004) · Zbl 1055.05092 |
| [12] | Krivelevich, M.; Yuster, R., The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory, 63, 185-191 (2009) · Zbl 1193.05079 |
| [13] | Lei, H.; Liu, H.; Magnant, C.; Shi, Y., Total rainbow connection of digraphs, Discrete Appl. Math., 236, 288-305 (2018) · Zbl 1377.05096 |
| [14] | Lei, H.; Li, S.; Liu, H.; Shi, Y., Rainbow vertex connection of digraphs, J. Comb. Optim., 35, 86-107 (2018) · Zbl 1386.05077 |
| [15] | Li, H.; Li, X.; Liu, S., Rainbow connection of graphs with diameter 2, Discrete Math., 312, 1453-1457 (2012) · Zbl 1237.05118 |
| [16] | Li, X.; Liu, S.; Chandran, L. S.; Mathew, R.; Rajendraprasad, D., Rainbow connection number and connectivity, Electron. J. Combin., 19, P20 (2012) · Zbl 1243.05133 |
| [17] | Li, X.; Shi, Y.; Sun, Y., Rainbow connections of graphs: a survey, Graphs Combin., 29, 1-38 (2013) · Zbl 1258.05058 |
| [18] | Li, X.; Sun, Y., Rainbow Connections of Graphs (2012), Springer: Springer New York · Zbl 1250.05066 |
| [19] | Lick, D. R.; White, A. T., k-Degenerate graphs, Can. J. Math., 22, 1082-1096 (1970) · Zbl 0202.23502 |
| [20] | Liu, H.; Mestre, A.; Sousa, T., Total rainbow k-connection in graphs, Discrete Appl. Math., 174, 92-101 (2014) · Zbl 1298.05127 |
| [21] | Liu, Y.; Wang, Z., Rainbow connection number of the thorn graph, Appl. Math. Sci., 8, 6373-6377 (2014) |
| [22] | Lu, Z.; Ma, Y., Rainbow 2-connection numbers of Cayley graphs, Inform. Process. Lett., 115, 486-491 (2015) · Zbl 1306.05069 |
| [23] | Ma, Y., Total rainbow connection number and complementary graph, Results Math., 70, 173-182 (2016) · Zbl 1344.05064 |
| [24] | Ma, Y.; Chen, L.; Li, H., Graphs with small total rainbow connection number, Front. Math. China, 12, 921-936 (2017) · Zbl 1371.05090 |
| [25] | Ma, Y.; Chen, L.; Li, H.; Li, H., The total rainbow connection numbers of cubic graphs, Utliltas Math., 99, 143-150 (2016) · Zbl 1345.05030 |
| [26] | Schiermeyer, I., On mininally rainbow k-connected graphs, Discrete Appl. Math., 161, 702-705 (2013) · Zbl 1259.05102 |
| [27] | Sun, Y., On rainbow total-coloring of a graph, Discrete Appl. Math., 194, 171-177 (2015) · Zbl 1319.05057 |
| [28] | Uchizawa, K.; Aoki, T.; Ito, T.; Suzuki, A.; Zhou, X., On the rainbow connectivity of graphs: complexity and FPT algorithms, Algorithmica, 67, 161-179 (2013) · Zbl 1290.68060 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
