Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called Θ-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1644,
author = {Sandi Klav\v zar and Ga\v sper Meki\v s},
title = {On the rainbow connection of Cartesian products and their subgraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {783-793},
zbl = {1293.05112},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1644}
}
Sandi Klavžar; Gašper Mekiš. On the rainbow connection of Cartesian products and their subgraphs. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 783-793. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1644/
[000] [1] M. Basavaraju, L.S. Chandran, D. Rajendraprasad and A. Ramaswamy, Rainbow connection number of graph power and graph products, manuscript (2011) arXiv:1104.4190 [math.CO]. | Zbl 1306.05203
[001] [2] Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57. | Zbl 1181.05037
[002] [3] S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21 (2011) 330-347, doi: 10.1007/s10878-009-9250-9. | Zbl 1319.05049
[003] [4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. | Zbl 1199.05106
[004] [5] T. Gologranc, G. Mekiš and I. Peterin, Rainbow connection and graph products, IMFM Preprint Series 49 (2011) #1149.
[005] [6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs: Second Edition (CRC Press, Boca Raton, 2011). | Zbl 1283.05001
[006] [7] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Products (A K Peters, Wellesley, 2008). | Zbl 1156.05001
[007] [8] A. Kemnitz and I. Schiermeyer, Graphs with rainbow connection number two, Discuss. Math. Graph Theory 31 (2011) 313-320, doi: 10.7151/dmgt.1547.
[008] [9] 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: 10.1002/jgt.20418. | Zbl 1193.05079
[009] [10] X. Li and Y. Sun, Characterize graphs with rainbow connection number m-2 and rainbow connection numbers of some graph operations, manuscript (2010).
[010] [11] X. Li and Y. Sun, Rainbow connection of graphs - A survey, manuscript (2011) arXiv:1101.5747v1 [math.CO].
[011] [12] I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31 (2011) 387-395, doi: 10.7151/dmgt.1553. | Zbl 1234.05132
[012] [13] P. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225. | Zbl 0529.05055