Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six

J. Cervantes-Ojeda, M. Gómez-Fuentes, D. González-Moreno and M. Olsen

Journal of Applied Mathematics, 2019, vol. 2019, issue 1

Abstract: A rainbow t-coloring of a t‐connected graph G is an edge coloring such that for any two distinct vertices u and v of G there are at least t internally vertex‐disjoint rainbow (u, v)‐paths. In this work, we apply a Rank Genetic Algorithm to search for rainbow t‐colorings of the family of Moore cages with girth six (t; 6)‐cages. We found that an upper bound in the number of colors needed to produce a rainbow 4‐coloring of a (4; 6)‐cage is 7, improving the one currently known, which is 13. The computation of the minimum number of colors of a rainbow coloring is known to be NP‐Hard and the Rank Genetic Algorithm showed good behavior finding rainbow t‐colorings with a small number of colors.

Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2019/4073905

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2019:y:2019:i:1:n:4073905

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().