Let be an edge-colored graph. A path of is said to be rainbow if no two edges of have the same color. An edge-coloring of is a rainbow-coloring if for any two distinct vertices and of there are at least internally vertex-disjoint rainbow -paths. The rainbow-connectivity of a graph is the minimum integer such that there exists a rainbow -coloring using colors. A -cage is a -regular graph of girth and minimum number of vertices denoted . In this paper we focus on . It is known that and when the -c...
Let be an edge-colored graph. A path of is said to be rainbow if no two edges of have the same color. An edge-coloring of is a rainbow-coloring if for any two distinct vertices and of there are at least internally vertex-disjoint rainbow -paths. The rainbow-connectivity of a graph is the minimum integer such that there exists a rainbow -coloring using colors. A -cage is a -regular graph of girth and minimum number of vertices denoted . In this paper we focus on . It is known that and when the -cage is called a Moore cage. In this paper we prove that the rainbow -connectivity of a Moore -cage satisfies that . It is also proved that the rainbow 3-connectivity of the Heawood graph is 6 or 7.
Citation
Balbuena, C., Fresán, J., González, D., Olsen, M. Rainbow connectivity of Moore cages of girth 6. "Discrete applied mathematics", 11 Desembre 2018, vol. 250, p. 104-109.
Rainbow+connectivity+of+Moore+cages+of+girth+6PROOFS.pdf
(460543 bytes)
Share
