×

Rainbow 2-connection numbers of Cayley graphs. (English) Zbl 1306.05069

Summary: A path in an edge colored graph is said to be a rainbow path if no two edges on this path share the same color. For an \(l\)-connected graph \(\Gamma\) and an integer \(k\) with \(1\leq k\leq l\), the rainbow \(k\)-connection number of \(\Gamma\) is the minimum number of colors required to color the edges of \(\Gamma\) such that any two distinct vertices of \(\Gamma\) are connected by \(k\) internally disjoint rainbow paths. In this paper, a method is provided for bounding the rainbow 2-connection numbers of graphs with certain structural properties. Using this method, we consider the rainbow 2-connection numbers of Cayley graphs, especially, those defined on abelian groups and dihedral groups.

MSC:

05C15 Coloring of graphs and hypergraphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 555-566 (1989) · Zbl 0678.94026
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001
[3] Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., Rainbow connection in graphs, Math. Bohem., 133, 85-98 (2008) · Zbl 1199.05106
[4] Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., The rainbow connectivity of a graph, Networks, 54, 75-81 (2009) · Zbl 1205.05124
[5] Fujie-Okamoto, F.; Johns, G. L.; Zhang, P., The rainbow connectivities of small cubic graphs, Ars Comb., 105, 129-147 (2012) · Zbl 1274.05166
[6] Fujita, S.; Liu, H.; Magnant, C., Rainbow \(k\)-connection in dense graphs (extended abstract), Electron. Notes Discrete Math., 38, 361-366 (2011) · Zbl 1274.05157
[7] Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer: Springer New York · Zbl 0968.05002
[8] He, J.; Liang, H. Y., On rainbow \(k\)-connectivity of random graphs, Inf. Process. Lett., 112, 406-410 (2012) · Zbl 1243.05218
[9] Li, H. Z.; Li, X. L.; Liu, S. J., The (strong) rainbow connection numbers of Cayley graphs on Abelian groups, Comput. Math. Appl., 62, 4082-4088 (2011) · Zbl 1235.05063
[10] Li, X. L.; Liu, S. J., A sharp upper bound for the rainbow 2-connection number of a 2-connected graph, Discrete Math., 313, 755-759 (2013) · Zbl 1260.05062
[11] Li, X. L.; Sun, Y. F., Note on the rainbow \(k\)-connectivity of regular complete bipartite graphs, Ars Comb., 101, 513-518 (2011) · Zbl 1265.05236
[12] Li, X. L.; Sun, Y. F., Rainbow Connections of Graphs (2012), Springer: Springer New York · Zbl 1250.05066
[14] Menger, K., Zur allgemeinen Kurventheorie, Fundam. Math., 10, 96-115 (1927) · JFM 53.0561.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.