The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths

Bety Hayat Susanti, A.N.M. Salman, Rinovia Simanjuntak

Abstract


An edge-colored graph G is rainbow k-connected, if there are k-internally disjoint rainbow paths connecting every pair of vertices of G. The rainbow k-connection number of G, denoted by rck(G), is the minimum number of colors needed for which there exists a rainbow k-connected coloring for G. In this paper, we are able to find sharp lower and upper bounds for the rainbow 2-connection number of Cartesian products of arbitrary 2-connected graphs and paths. We also determine the rainbow 2-connection number of the Cartesian products of some graphs, i.e. complete graphs, fans, wheels, and cycles, with paths.


Keywords


Cartesian product, 2-connected graph, rainbow $2$-connectivity, rainbow path

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.11

References

M. Basavaraju, L. S. Chandran, D. Rajendraprasad, and A. Ramaswamy, Rainbow connection number of graph power and graph products, Graphs and Combinatorics 30:6 (2014) 1363–1382.

S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connectivity, Journal of Combinatorial Optimization 21 (2011) 330–347.

G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, Rainbow connection in graphs, Mathematica Bohemica 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.

G. Chartrand and P. Zhang, A First Course in Graph Theory (Dover Publications, 2012).

R. Deniawanty and A. N. M. Salman, The rainbow connection number of an n-crossed prism graph and its corona product with a trivial graph, Procedia Computer Science 74 (2015) 143–150.

D. Fitriani and A. N. M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE International Journal of Combinatorics 13:1 (2016) 90–99.

S. Fujita, H. Liu, and C. Magnant, Rainbow k-connection in dense graphs, Electronic Notes in Discrete Mathematics 38 (2011) 361–366.

T. Gologranc, G. Mˇekis, and I. Peterin, Rainbow connection and graph products, Graphs and Combinatorics 30:3 (2014) 591–607.

R. Hammack, W. Imrich, and S. Klavˇzar, Handbook of Product Graphs 2ed. (Taylor and Francis Group, 2011).

J. He and H. Liang, On rainbow k-connectivity of random graphs, Information Processing Letters 112:10 (2014) 406–410.

D. F. Hsu and T. Łuczak, Note on the k-diameter of k-regular k-connected graphs, Discrete Mathematics 133 (1994) 291–296.

X. Li and Y. Sun, On the rainbow k-connectivity of complete graphs, Australasian Journal of Combinatorics 49 (2011) 217–226.

X. Li and Y. Sun, Characterization of graphs with large rainbow connection number and rainbow connection numbers of some graph operations, preprint.

X. Li, Y. Shi, and Y. Sun, Rainbow connections of graphs: a survey, Graphs and Combinatorics 29 (2013) 1–38.

X. Li and S. Liu, A sharp upper bound for the rainbow 2-connection number of a 2-connected graph, Discrete Mathematics 313 (2013) 755–759.

X. Li and Y. Sun, An updated survey on rainbow connections of graphs - a dynamic survey, Theory and Applications of Graphs 0:1 (2017) article 3.

Z. Lu and Y. Ma, Rainbow 2-connection numbers of Cayley graphs, Information Processing Letters 115 (2015) 486–491.

B. H. Susanti, A. N. M. Salman, and R. Simanjuntak, Upper bounds for rainbow 2-connetivity of the Cartesian product of a path and a cycle, Procedia Computer Science 74 (2015) 151–154.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats