Rainbow connection number of corona product of graphs
Abstract
In an edge-colored graph (where adjacent edges may have the same color), a rainbow path is a path whose edge colors are all distinct. The coloring is called a rainbow coloring if any two vertices can be connected by a rainbow path. The rainbow connection number rc(G) is the smallest number of colors in a rainbow coloring of G. The corona product G ∘ H of two graphs G and H is constructed from one copy of G and n = |V (G)| disjoint copies of H such that the i-th vertex of G is joined to all vertices in the i-th copy of H, for each i ∈{1,…,n}. Several resuls on the rainbow connection number of corona product have been published, but there are inaccuracies. In this paper, we close the gaps and add new results. The strong variant of rainbow connection number is also discussed.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2024.12.2.14
References
J. A. Bondy and U. S. R. Morty, Graph Theory, Springer (2008)
R. P. Carpentier, H. Liu, M. Silva and T. Sousa, Rainbow connection for some families of hypergraphs, Discrete Math. 327 (2014), 40-50. DOI: https://doi.org/10.1016/j.disc.2014.03.013
S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21 (3) (2011), 330–347. DOI:10.1007/s10878-009-9250-9
L. S. Chandran, A. Das, D. Rajendraprasad, and N. M. Varma. Rainbow connection number and connected dominating sets. J. Graph Theory 71 (2012), 206–218
G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang. Rainbow connection in graphs, Math. Bohem 133 (2008), 85–98
G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2) (2009), 75–81
P. Dorbec, I. Schiermeyer, E. Sidorowicz, and E. Sopena, Rainbow connection in oriented graphs, Discrete Appl. Math. 179 (2014), 69–78. DOI: https://doi.org/10.1016/j.dam.2014.07.018
L. A. Dupont, D. G. Mendoza, and M. Rodriguez, The rainbow connection number of the enhanced power graph of a finite group, Electron. J. Graph Theory Appl. 11 (1) (2023), 235–244. DOI: https://dx.doi.org/10.5614/ejgta.2023.11.1.19
D. Estetikasari and S. Sy, On the rainbow connection for some corona graphs, Appl. Math. Sci. 7 (2013), 4975–4980. DOI: http://dx.doi.org/10.12988/ams.2013.37410
D. Fitriani, A. N. M. Salman, and Z. Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl. 10 (2) (2022), 461–473. DOI: https://dx.doi.org/10.5614/ejgta.2022.10.2.9
R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970), 322–325
J. A. Gallian, A dynamic survey of graph labelling, Electron. J. Combin. (2022) DS#6
M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185–191. DOI: https://doi.org/10.1002/jgt.20418
X. Li and Y. Sun, Rainbow connection numbers of line graphs. Ars Comb. 100 (2011), 449–463
X. Li and Y. Sun, Rainbow Connections of Graphs, Springer (2012). DOI: https://doi.org/10.1007/978-1-4614-3119-0
X. Li and Y. Sun, An updated survey of rainbow connections of graphs—a dynamic survey, Theory Appl. Graphs 0 (2017) Article 3. DOI: https://doi.org/10.20429/tag.2017.000103
Y. Liu and Z. Wang, The Rainbow Connection of Windmill and Corona Graph, Appl. Math. Sci. 8 (128) (2014), 6367–6372. DOI: http://dx.doi.org/10.12988/ams.2014.48632
A. Maulani, S. F. Y. O. Pradini, D. Setyorini, and K. A. Sugeng, Rainbow connection number of Cm ∘ Pn and Cm ∘ Cn, Indonesian Journal of Combinatorics 3 (2019), 95–108.
I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31 (2011), 387–395
F. Septyanto, Bilangan keterhubungan pelangi pada sequential join dari empat atau lima graf, Journal of Mathematics and Its Applications 18(1) (2022), 77–85. DOI: https://doi.org/10.29244/milang.18.1.77-85
F. Septyanto and K. A. Sugeng, Rainbow connections of graph joins, Australas. J. Combin.: Special Issue in Memory of Mirka Miller, 69 (2017), 375–381
F. Septyanto and K. A. Sugeng, Color code techniques in rainbow connection, Electron. J. Graph Theory Appl. 6 (2) (2018), 1–13. DOI: https://dx.doi.org/10.5614/ejgta.2018.6.2.14
F. Septyanto and K. A. Sugeng, Distance-local rainbow connection number, Discuss. Math. Graph Theory, 42 (2022), 1027–1039. DOI: https://doi.org/10.7151/dmgt.2325
Y. Sun, On rainbow total-coloring of a graph, Discrete Appl. Math. 194 (2015), 171–177. DOI: https://doi.org/10.1016/j.dam.2015.05.012
Y. Sun, Rainbow connection numbers for undirected double-loop networks. In: Gao, D., Ruan, N., Xing, W. (eds) Advances in Global Optimization. Springer Proceedings in Mathematics & Statistics 95 (2015), Springer, Cham.
B. H. Susanti, A. N. M. Salman, and R. Simanjuntak, The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths, Electron. J. Graph Theory Appl. 8 (1) (2020), 145–156. DOI: https://dx.doi.org/10.5614/ejgta.2020.8.1.11
S. Sy, G. H. Medika, and L. Yulianti, The rainbow connection of fan and sun, Appl. Math. Sci. 7 (2013), 3155-3159
R. F. Umbara, A. N. M. Salman, and P. E. Putri, On the inverse graph of a finite group and its rainbow connection number, Electron. J. Graph Theory Appl. 11 (1) (2023), 135–147. DOI: https://dx.doi.org/10.5614/ejgta.2023.11.1.11
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.