Discussiones Mathematicae Graph Theory 32(4) (2012)
783-793

doi: 10.7151/dmgt.1644

Sandi Klavžar
Faculty of Mathematics and Physics, University of Ljubljana | Gašper Mekiš
Institute of Mathematics, Physics and Mechanics |

**Keywords:** rainbow connection, strong rainbow connection, Cartesian product of graphs, isometric subgraph, hypercube

**2010 Mathematics Subject Classification:** 05C15, 05C76, 05C12.

[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]. |

[2] | Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57. |

[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. |

[4] | G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85--98. |

[5] | T. Gologranc, G. Mekiš and I. Peterin, Rainbow connection and graph products, IMFM Preprint Series 49 (2011) #1149. |

[6] | R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs: Second Edition (CRC Press, Boca Raton, 2011). |

[7] | W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Products (A K Peters, Wellesley, 2008). |

[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. |

[9] | M. Krivelevich and R. Yuster, The rainbow connection of a graph is , J. Graph Theory (at most) reciprocal to its minimum degree 63 (2010) 185--191, doi: 10.1002/jgt.20418. |

[10] | X. Li and Y. Sun, Characterize graphs with rainbow connection number , manuscript m-2 and rainbow connection numbers of some graph operations (2010). |

[11] | X. Li and Y. Sun, Rainbow connection of graphs -- A survey, manuscript (2011) arXiv:1101.5747v1 [math.CO]. |

[12] | I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31 (2011) 387--395, doi: 10.7151/dmgt.1553 . |

[13] | P. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7 (1984) 221--225. |

Received 8 June 2011

Revised 6 February 2012

Accepted 6 February 2012