Rainbow Connection and Graph Products
作者： Tanja Gologranc , Gašper Mekiš , Iztok Peterin
DOI: 10.1007/S00373-013-1295-Y
关键词:
摘要: A path in an edge colored graph G is called a rainbow if all its edges have pairwise different colors. Then connected there exists between every pair of vertices and the least number colors needed to obtain connection number. If we demand that must exist shortest vertices, speak about strongly strong In this paper study (strong) on direct, strong, lexicographic product present several upper bounds for these products are attained by many graphs. Several exact results also obtained.
springer.com
imfm.si参考文章(22)
Ghidewon Abay-Asmerom, Richard Hammack, Centers of Tensor Products of Graphs. Ars Combinatoria. ,vol. 74, ,(2005)
Yair Caro, Arie Lev, Yehuda Roditty, Zsolt Tuza, Raphael Yuster, On Rainbow Connection Electronic Journal of Combinatorics. ,vol. 15, pp. 57- ,(2008) , 10.37236/781
Simon Špacapan, Connectivity of Strong Products of Graphs Graphs and Combinatorics. ,vol. 26, pp. 457- 467 ,(2010) , 10.1007/S00373-010-0919-8
Iztok Peterin, Intervals and Convex Sets in Strong Product of Graphs Graphs and Combinatorics. ,vol. 29, pp. 705- 714 ,(2013) , 10.1007/S00373-012-1144-4
Gary Chartrand, Ping Zhang, Garry L. Johns, Kathleen A. McKeon, The rainbow connectivity of a graph Networks. ,vol. 54, pp. 75- 81 ,(2009) , 10.1002/NET.V54:2
Xueliang Li, Yuefang Sun, Rainbow Connection of Graphs -- A Survey ,(2011)
Game coloring the Cartesian product of graphs Journal of Graph Theory. ,vol. 59, pp. 261- 278 ,(2008) , 10.1002/JGT.V59:4
Pranava K. Jha, Sandi Klavžar, Blaž Zmazek, Isomorphic components of Kronecker product of bipartite graphs Discussiones Mathematicae Graph Theory. ,vol. 17, pp. 301- 309 ,(1997) , 10.7151/DMGT.1057
K. Seyffarth, R. J. Nowakowski, Small cycle double covers of products I: Lexicographic product with paths and cycles Journal of Graph Theory. ,vol. 57, pp. 99- 123 ,(2008) , 10.1002/JGT.V57:2
Ingo Schiermeyer, Bounds for the rainbow connection number of graphs Discussiones Mathematicae Graph Theory. ,vol. 31, pp. 387- 395 ,(2011) , 10.7151/DMGT.1553