On rainbow connection number of cartesian product of graphs

Articles in Press

Document Type : Research Paper

Authors

Department of Mathematical Sciences, Shahid Beheshti University, G.C., P.O. Box 19839-63113, Tehran, Iran.

10.48308/cgasa.2026.242084.1578

Abstract

Edge coloring of a graph is a function from its edge set to the set of natural numbers (called colours). A path in an edge-colored graph with no two edges sharing the same color is called a rainbow path. An edge-colored graph is said to be rainbow connected if every pair of vertices is connected by at least one rainbow path. Such a coloring is called a rainbow coloring of the graph. The minimum number of colors required to rainbow color a connected graph is called its rainbow connection number, denoted by $rc(G)$. For example, the rainbow connection number of a complete graph is 1, that of a path is its length, and that of a star is its number of leaves. For a basic introduction to the topic, see Chapter 11 in \cite{Ch2} and for a comprehensive treatment of the area see the recent monograph by Li and Sun \cite{Li}. The concept of rainbow coloring was introduced in \cite{Ch1}.

Keywords

Main Subjects

References

[1] Ericksen, A.B., “A matter of security”, Graduating Engineer and Computer Careers (2008), 24-28.
[2] Basavaraju, M., Chandran, L.S., Rajendraprasad, D., and Ramaswamy, A., Rainbow connection number of graph power and graph products, Graphs and Combinatorics 30 (2014), 1363-1382.
[3] Chartrand, G., Johns, G.L., McKeon, K.A., and Zhang, P., Rainbow connection in graphs, Math. Bohem. 133(1) (2008), 85-98.
[4] Chartrand, G. and Zhang, P., “Chromatic Graph Theory”, Chapman & Hall, 2008.
[5] Surbakti, N.M., Silaban, D.R., and Sugeng, K.A., The rainbow connection number of graph resulting for operation of sun graph and path graph, AIP Conference Proceedings 2242 (2020).
[6] Li, X. and Sun, Y., “Rainbow Connections of Graphs”, Springer Briefs in Mathematics, Springer, Berlin, 2012.
[7] Chithra, M.R. and Vijayakumar, A., The diameter variability of the Cartesian product of graphs, Discrete Math. Algorithms Appl. 6(1) (2014), Paper No. 1450001.
Categories and General Algebraic Structures with Applications

Articles in Press, Accepted Manuscript
Available Online from 05 April 2026

Files

Share

How to cite

Statistics