Rainbow vertex-connection and graph products

References

• B.S. Anand, M. Changat, S. Klavz˘ar, and I. Peterin, Convex sets in lexicographic products of graphs, Graphs Combin. 28 (2012), pp. 77–84. doi: 10.1007/s00373-011-1031-4
   Web of Science ®Google Scholar
• F. Bao, Y. Igarashi, and S.R. Öhring, Reliable broadcasting in product networks, Discrete Appl. Math. 83 (1998), pp. 3–20. doi: 10.1016/S0166-218X(97)00100-5
   Web of Science ®Google Scholar
• M. Basavaraju, L.S. Chandran, D. Rajendraprasad, and A. Ramaswamy, Rainbow connection number of graph power and graph product, arXiv: 1104.4190 [math.CO], 2011.
   Google Scholar
• J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008, GTM 244.
   Google Scholar
• B. Brešar and S. Špacapan, On the connectivity of the direct product of graphs, Austral. J. Combin. 41 (2008), pp. 45–56.
   Google Scholar
• N.J. Calkin and H.S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math. 11(1) (1998), pp. 54–60. doi: 10.1137/S089548019528993X
   Web of Science ®Google Scholar
• Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008), paper no. R57. Available at http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r57/pdf
   Web of Science ®Google Scholar
• S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connectivity, 26th International Symposium on Theoretical Aspects of Computer Science STACS (2009), Freiburg, 243–254. Also, see J. Combin. Optim. 21(2011), 330–347.
   Google Scholar
• G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008), pp. 85–98.
   Google Scholar
• G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009), pp. 75–81. doi: 10.1002/net.20296
   Web of Science ®Google Scholar
• L. Chen, X. Li, and Y. Shi, The complexity of determining the rainbow vertex-connection of a graph, Theoret. Comput. Sci. 412 (2011), pp. 4531–4535. doi: 10.1016/j.tcs.2011.04.032
   Web of Science ®Google Scholar
• S.K. Das, S.R. Öhring, and A.K. Banerjee, Embeddings into hyper Petersen networks: Yet another hypercube-like interconnection topology, VLSI Des. 2(4) (1995), pp. 335–351. doi: 10.1155/1995/95759
   Web of Science ®Google Scholar
• K. Day and A.-E. Al-Ayyoub, The cross product of interconnection networks, IEEE Trans. Parallel Distrib. Syst. 8(2) (1997), pp. 109–118. doi: 10.1109/71.577251
   Web of Science ®Google Scholar
• A. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007), pp. 24–28.
   Google Scholar
• P. Fragopoulou, S.G. Akl, and H. Meijer, Optimal communication primitives on the generalized hypercube network, IEEE Trans. Parallel Distrib. Comput. 32(2) (1996), pp. 173–187. doi: 10.1006/jpdc.1996.0012
   Web of Science ®Google Scholar
• A.A. Ghidewon and R. Hammack, Centers of tensor product of graphs, Ars. Combin. 74 (2005), pp. 201–211.
   Web of Science ®Google Scholar
• T. Gologranc, G. Mekiš, and I. Peterin, Rainbow connection and graph products, 30(3) (2014), pp. 591–607.
   Google Scholar
• R. Guji and E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009), pp. 1360–1363. doi: 10.1016/j.aml.2009.03.008
   Web of Science ®Google Scholar
• R. Hammack, W. Imrich, and S. Klavz˘r, Handbook of product graphs, 2nd ed., CRC Press, New York, 2011.
   Google Scholar
• A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Inform. Comput. 79 (1988), pp. 43–59. doi: 10.1016/0890-5401(88)90016-8
   Web of Science ®Google Scholar
• P.K. Jha, S. Klavžar, and B. Zmazek, Isomorphic components of Kronecker product of bipartite graphs, Discuss. Math. Graph Theory 17 (1997), pp. 301–309. doi: 10.7151/dmgt.1057
   Google Scholar
• S.L. Johnsson and C.-T. Ho, Optimum broadcasting and personalized communication in hypercubes, IEEE Trans. Comput. 38(9) (1989), pp. 1249–1268. doi: 10.1109/12.29465
   Web of Science ®Google Scholar
• S.R. Kim, Centers of a tensor composite graph, Congr. Numer. 81 (1991), pp. 193–203.
   Google Scholar
• S. Klavžar and G. Mekiš, On the rainbow connection of Cartesian products and their subgraphs, Discuss. Math. Graph Theory 32 (2012), pp. 783–793. doi: 10.7151/dmgt.1644
   Web of Science ®Google Scholar
• S. Klavžar and S. Špacapan, On the edge-connectivity of Cartesian product graphs, Asian-Eur. J. Math. 1 (2008), pp. 93–98. doi: 10.1142/S1793557108000102
   Google Scholar
• M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2009), pp. 185–191.
   Web of Science ®Google Scholar
• M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree three, IWOCA 2009, LNCS 5874(2009), 432–437.
   Google Scholar
• S. Ku, B. Wang, and T. Hung, Constructing edge-disjoint spanning trees in product networks, IEEE Trans. Parallel Distrib. Syst. 14(3) (2003), pp. 213–221. doi: 10.1109/TPDS.2003.1189580
   Web of Science ®Google Scholar
• X. Li and S. Liu, Tight upper bound of the rainbow vertex-connection number for 2-connected graphs, Discrete Appl. Math. 173 (2014), pp. 1–112. doi: 10.1016/j.disc.2014.06.017
   Web of Science ®Google Scholar
• X.L. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory 33(2) (2013), pp. 307–313. doi: 10.7151/dmgt.1664
   Web of Science ®Google Scholar
• X. Li and Y. Sun, Rainbow Connections of Graphs, Springer Briefs in Math. Springer, New York, 2012.
   Google Scholar
• X. Li, Y. Mao, and Y. Shi, On the strong rainbow vertex-connection, Util. Math. 93 (2014), pp. 213–223.
   Web of Science ®Google Scholar
• X. Li, Y. Shi, and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29(1) (2013), pp. 1–38. doi: 10.1007/s00373-012-1243-2
   Web of Science ®Google Scholar
• Y. Mao, Path-connectivity of lexicographical product graphs, Int. J. Comput. Math. (2014). doi:10.1080/00207160.2014.987762.
   Web of Science ®Google Scholar
• R.J. Nowakowski and K. Seyffarth, Small cycle double covers of products I: Lexicographic product with paths and cycles, J. Graph Theory 57 (2008), pp. 99–123. doi: 10.1002/jgt.20265
   Web of Science ®Google Scholar
• I. Schiermeyer, Rainbow connection in graphs with minimum degree three, IWOCA 2009, LNCS 5874 (2009), 435–437.
   Google Scholar
• I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31 (2011), pp. 387–395. doi: 10.7151/dmgt.1553
   Google Scholar
• S. Špacapan, Connectivity of strong products of graphs, Graphs Combin. 26 (2010), pp. 457–467. doi: 10.1007/s00373-010-0919-8
   Web of Science ®Google Scholar
• P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962), pp. 47–52. doi: 10.1090/S0002-9939-1962-0133816-6
   Google Scholar
• X. Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59 (2008), pp. 261–278. doi: 10.1002/jgt.20338
   Web of Science ®Google Scholar