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

Authors: J. Cervantes-Ojeda; M. Gómez-Fuentes; D. González-Moreno; M. Olsen
Journal: Journal of Applied Mathematics
 (2019)

---

## Abstract

Arainbowt-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.


---

## Body

## 1. Introduction and Definitions

Evolutionary algorithms have been applied to a wide variety of engineering problems [1], and they have also been applied to mathematics problems. For instance, Jong and Spears [2] showed that Genetic Algorithms (GA) can be used to solve NP-Complete problems, [3] applied a GA to a geometry problem, and [4] solved nonlinear algebraic equations by using a GA. Here we have successfully applied a Rank Genetic Algorithm (Rank GA) [5] to the graph theory problem of finding the rainbow connection number of a graph (rc(G)). Chakraborty et al. [6] proved that, for a given graph G, deciding whether rc(G)=2 is NP-Complete and that it is also NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. Therefore, our motivation is to try using the Rank GA heuristic on this problem. To our best knowledge, this problem has not been approached in this way nor using any other heuristic algorithms.In a genetic algorithm we have an initial population of individuals; in our case, each individual represents a particular edge-colored graph. Each individual of the population is evaluated according to a fitness function; this function measures the ability of the individual for reaching a predetermined objective. Once individuals are evaluated, the next generation is obtained by applying genetic operators to the population inspired by the evolution in nature, such as cross-over between individuals, selection of the fittest individuals, and mutations. This procedure is repeated until the genetic algorithm finds an individual that achieves the required objective or until a maximum number of generations are reached. A genetic algorithm can solve mathematical problems that are intractable by exhaustive search, as is the case of the problem described here.A graphG is t-connected if and only if there are at least t internally disjoint (u,v)-paths connecting every two distinct vertices u and v of G [7]. Arainbow path is a path P such that all the edges of P have different colors (a path P of G is a sequence of distinct vertices (v1,v2,…,vn) such that vi,vi+1 is an edge for i∈1,2,…,n-1). An edge coloring of a graph is called arainbowt-coloring if for every pair of distinct vertices u and v there are at least t internally disjoint rainbow (u,v)-paths. Therainbowt-connectivityrct(G) (defined by Chartrand et al. [8]) of a graph G is the minimum integer j such that there exists an edge coloring using j colors which is a rainbow t-coloring. The rainbow 1-connectivity is known as therainbow connection number and was introduced by Chartrand et al. [9].The rainbowt-connectivity of a graph has applications in the Cybernetic Security (see Ericksen [10]). For any fixed k≥2, deciding if rc1(G)=k is NP-Complete [6, 11]. For more references on rainbow connectivity and rainbow t-connectivity we refer the reader to the survey by Li [12] et al. and the book of Li and Sun [13].A graphG is k-regular if every vertex of G has degree k. Thegirth of G is the length of a shortest cycle of G. Given two integers k≥2 and g≥3 a (k;g)-cage is a k-regular graph with girth g and the minimum possible number of vertices. Let n(k;g) denote the order of a (k;g)-cage. For references on cages see the dynamic survey of Exoo and Jajcay [14]. By counting the vertices emerging from a vertex or from an edge the lower bound n0(k;g), known as theMoore bound, is obtained. That is, n(k;g)≥n0(k;g), where(1)n0k;g=2∑i=0g-2/2k-1i=2k-1g/2-2k-2ifgis  even,1+∑i=1g-1/2kk-1i-1=kk-1g-1/2-2k-2ifgis  odd.When n(k;g)=n0(k;g) the (k;g)-cage is called aMoore(k;g)-cage; for references on Moore cages see [15]. The Moore cages have been characterized [16–18]. The existence of (k;6)-Moore cages is related to the existence of finite geometries. For instance, the (3;6)-cage is the incidence graph of Fano’s plane. Concerning connectivity of (k;6)-cages it has been proved that they are k-connected [19].Chartrand et al. [20] showed that the rainbow 3-connectivity of the (3;6)-cage (the Moore cage known as Heawood graph) is between 5 and 7 inclusive. Recently, Balbuena et al. [21] proved that it is not 5, and they bounded the rainbow k-connectivity of (k;6)-cages as follows: if G is a Moore (k;6)-cage, then(2)k≤rckG≤k2-k+1If G is a (k,6)-cage, then for k=3, k=4, and k=5, respectively, we have rc3(G)≤7, rc4(G)≤13, and rc5(G)≤21, respectively. In this paper we use a genetic algorithm to search for rainbow k-colorings of (k;6)-cages with k=3 and k=4 [21] in order to see if the upper bound for rck(G) can be improved.The structure of this paper is as follows. In Section2 we explain how the Rank GA was applied to the rainbow coloring problem. Results are presented in Section 3 and finally the conclusions are drawn in Section 4.


## 2. Finding Rainbow Colorings in a Moore Cage with a Genetic Algorithm

Finding a particular rainbowt-coloring of a graph G using r colors (that is a coloring with t internally disjoint rainbow paths between any pair of vertices) implies that rct(G)≤r. We use an adapted version of the Rank GA [5] to find rainbow colorings in a Moore cage. To do so, each individual in the population contains a list of the assigned colors of each edge in the graph and is initialized randomly. In the Rank GA, the individuals of the population are ranked from best to worst in terms of their fitness before the genetic operators (selection, recombination and mutation) are applied. The application of these genetic operators depends on the rank of each individual in the population. The top ranked individuals tend to vary less than the bottom ranked ones. This is to make the latter try to escape from local optima of the fitness function. Also, top ranked individuals tend to be cloned more than others who tend to disappear.The adapted RankGA pseudocode that was used is given in Algorithm1 and its parameters are shown in Table 1.Table 1
Parameters of the Rank GA.
Description Value Population size = E G Number of Generations No limit Population’s selective pressureS 3Algorithm 1:Rank GA.
procedureRankGA n u m I n d i v i d u a l s ← | E ( G ) | P o p u l a t i o n I n i t i a l i z a t i o n E v a l u a t i o n and Sort whilenot end Criteria metdo R a n k S e l e c t i o n R a n k R e c o m b i n a t i o n E v a l u a t i o n and Sort R a n k M u t a t i o n E v a l u a t i o n and Sort procedureRank Selection c l o n e s ← n u l l for i in [0..numIndividuals-1]do r ← i / ( n u m I n d i v i d u a l s - 1 ) n ← S ( 1 - r ) ( S - 1 ) for j in [0..n-1]do c l o n e s . a d d ( i n d i )  ⊳ i n d i is cloned n times i ← 0 while c l o n e s . s i z e ( ) < n u m I n d i v i d u a l s do r ← i / ( n u m I n d i v i d u a l s - 1 ) n ← S 1 - r ( S - 1 ) f ← n - n  ⊳ f is the fractional part of n if r a n d o m ( 0,1 ) < f then c l o n e s . a d d ( i n d i )  ⊳ one extra clone of indi i ← ( i + 1 ) mod numIndividuals i n d ← c l o n e s  ⊳ replace population S o r t procedureRank Recombination for i in [0..numIndividuals-2] step 2do for j in [0..numGenes-1]do if r a n d o m ( 0,1 ) < 0.5 then Switch(gi,j, gi+1,j) ⊳ mating is with indi+1 procedureRank Mutation for i in [0..numIndividuals-1]do r ← i / ( n u m I n d i v i d u a l s - 1 ) for j in [0..numGenes-1]do if r a n d o m ( 0,1 ) < r then g i , j ← random integer in the range [0..numColors-1]


### 2.1. The Fitness Function

We detail below the fitness function. As this is an interdisciplinary work, we express the fitness function mathematically (below) and also in a computational way in Algorithm2.Algorithm 2:Coloring fitness function.
function c o l o r i n g F i t n e s s ( c o l o r i n g ) r e s u l t ← 1 forEach vertex pair a in the Graphdo r ← p a i r F i t n e s s ( a , c o l o r i n g ) r e s u l t ← r e s u l t ∗ r  ⊳ Accumulate the product return result function p a i r F i t n e s s a , c o l o r i n g r e s u l t ← 0 forEach InternallyDisjointPathsSet DPSk of pair ado r ← d p s F i t n e s s ( D P S k , c o l o r i n g ) if r > r e s u l t then r e s u l t ← r  ⊳ Select best fitness return result function d p s F i t n e s s ( D P S k , c o l o r i n g ) r e s u l t ← 1 forEach Path p in DPSkdo r ← p a t h F i t n e s s ( p , c o l o r i n g ) r e s u l t ← r e s u l t ∗ r  ⊳ Accumulate the product return result function p a t h F i t n e s s ( p , c o l o r i n g ) r e s u l t ← p a t h N u m C o l o r s ( p , c o l o r i n g ) / p a t h . s i z e return result function p a t h N u m C o l o r s ( p , c o l o r i n g ) c o u n t ← 0 forEach Step s in pdo c ← c o l o r i n g [ s . s o u r c e ] [ s . d e s t ] ifnot used[c]then⊳ count colors only once c o u n t ← c o u n t + 1 u s e d [ c ] ← t r u e  ⊳ mark color as already used return countLetG be a graph, let Ψ(G) be the set of all possible colorings of the edges E(G), and let A be the set of all pairs of vertices of G, that is, A=a1,a2∣a1,a2∈V(G). The fitness function to be maximized using the RankGA is given as(3)coloringFitness:ΨG→R0,1(4)coloringFitnessψ=∏a∈ApairFitnessa,ψ1/Awhere ψ∈Ψ(G) and(5)pairFitness:A×ΨG→R0,1(6)pairFitnessa,ψ=maxPak∈DPSka⁡dpsFitnessPak,ψwhere DPSk(a) is the set of all sets Pak of k internally disjoint paths between the vertices in a and(7)dpsFitness:DPSka×ΨG→R0,1(8)dpsFitnessPak,ψ=∏p∈PakpathFitnessp,ψ1/Pakwhere(9)pathFitness:Pak×ΨG→R0,1(10)pathFitnessp,ψ=pathNumColorsp,ψEpwhere E(p) is the set of all edges in path p and(11)pathNumColors:Pak×ΨG→R0,1(12)pathNumColorsp,ψ=⋃e∈Epψewhere ψ(e) is the color that the coloring ψ assigns to edge e.The functionpathNumColors, in (12), calculates the cardinality of a set made out of the colors ψ(e) assigned to the edges e∈E(p) in path p. The function pathFitness, in (10), calculates the ratio of the pathNumColors over the length of path p, being this a value in the range 1/Ep,1, yielding 1 only in case the path has a rainbow coloring and lower values as the number of colors used in the path is reduced. The function dpsFitness, in (8), calculates the geometric mean of all the pathFitness values of all the k+1 paths p in the disjoint path set Pak, yielding a value in the range [0,1] with 1 representing a rainbow disjoint path set. The function pairFitness, in (6), returns the maximum dpsFitness that can be obtained from the set of disjoint path sets DPSk(a) between the vertices in the vertex pair a yielding 1 if and only if there existsat least one rainbow disjoint path set Pak in DPSk(a). Finally, the function coloringFitness in (4) computes the geometric mean of all the pairFitness values yielding a result that is 1 if and only if all pairs of vertices a have a fitness value of 1; i.e., the given coloring ψ is a rainbow coloring.The pseudocode of the fitness function is given in Algorithm2.


### 2.2. Finding the Set of Internally Disjoint Paths Sets between Pairs of Vertices in a Graph

The total number of possible setsPak of k paths (internally disjoint or not) between the vertices in pair a is very high as k grows so in order to save computing time when calculating the fitness of an individual, the function pairFitness in (6) iterates only on the elements of the set DPSk(a) which is the set of path sets Pak that contain k internally disjoint paths between the vertices in a. Algorithm 3 describes a way to calculate and store the set of all DPSk(a).Algorithm 3:Disjoint paths sets between vertices.
procedure s t o r e D i s j o i n t P a t h s S e t s G i n i t V e r t e x N e i g h b o r s  ⊳ set the neighbors of each vertex for current k forEach a∈A={{a1,a2}|a1,a2∈V(G)}do p a t h s [ a ] ← g e t P a t h s ( a , G , n u m C o l o r s ) d i s j o i n t P a t h s S e t s [ a ] ← g e t D i s j o i n t P a t h s S e t s ( p a t h s [ a ] , k ) function recursive g e t P a t h s ( a , G , m a x L e n g t h ) if m a x L e n g t h ≤ 0 then  ⊳ wrong length return null if v i s i t e d [ a 1 ] then  ⊳ a 1 has already been visited return null⊳ No paths to a2 if a 1 = a 2 then  ⊳ destination reached p ← { a 2 }  ⊳ single vertex in path return {p}⊳ single path in the set v i s i t e d [ a 1 ] ← t r u e for i = 1 to k+1do n e x t P a i r ← { n e i g h b o r [ i ] ( a 1 ) , a 2 }  ⊳ i t h neighbor of a1 s u b R e s u l t ← g e t P a t h s ( n e x t P a i r , G , m a x L e n g t h - 1 ) forEach path p in subResultdo n e w P a t h ← { a 1 } ⌢ p  ⊳ concatenate paths r e s u l t ← r e s u l t ∪ n e w P a t h  ⊳ aggregate path v i s i t e d [ a 1 ] ← f a l s e return result function g e t D i s j o i n t P a t h s S e t s ( P a , k ) forEach path set Pak of k paths p∈Pado⊳ may have huge # of iterations v i s i t e d ← f a l s e forEach internal vertex v of pdo if v i s i t e d [ v ] then next Pak v i s i t e d [ v ] ← t r u e r e s u l t ← r e s u l t ∪ P a k return resultIn this algorithm, the procedurestoreDisjointPathsSets takes each vertex pair a in G and calls function getPaths in order to get the full set Pa of paths p between the vertices in a with length l≤numColors (since longer paths cannot be rainbow colored). Then it calls another function getDisjointPathsSets which tests each set Pak containing k paths p∈Pa between the vertices in a to see if Pak is a disjoint paths set and returns the set DPSk(a) of disjoint paths sets Pak.The functiongetPaths is recursive and takes 3 parameters: a vertex pair a=a1,a2, a graph G, and a maximum length maxLength of the paths to be found. Figure 1 illustrates how this function works. Paths that go from vertex a1 to vertex a2 are made by adding the step from a1 to neighbori of a1 to all paths that go from neighbori of a1 to a2 for each i. But before doing this, vertex a1 is marked as visited in order to avoid paths that visit a vertex more than once. After computing the set of paths, vertex a1 is unmarked.Figure 1
Recursive finding of the set of paths between verticesa1 and a2.In Table2 we show how several measures grow with parameter k. First there is the number of vertices |V(G)| in the (k;6) cage followed by the total number of vertex pairs. Then there is the number of vertex pairs with distances d=1, d=2, and d=3 between them, respectively. We can see how the total number of paths with length l≤7=numColors between vertex pairs changes with distance d and with k. The next measure is the important one because it shows the drastic increase with k of the total number of paths sets containing k paths (internally disjoint and noninternally disjoint) that can be formed with the paths between the pairs of vertices with distances d=1, d=2, and d=3 between them, respectively. All these sets need to be tested to see which of them are disjoint pats sets. Finally we show the total number of paths sets that need to be tested and the approximate time to compute this with our existing algorithms and computing power. As one can see the numbers are much bigger as k increases making it practically impossible, at the moment, to do the work for k=5.Table 2
Growth withk of the effort to find the sets of disjoint paths sets.
k 3 4 5  VG 14 26 42  vertex pairs 91 325 861  vertex pairs with d = 1 21 52 105  vertex pairs with d = 2 42 156 420  vertex pairs with d = 3 28 117 336  paths for pairs with d = 1 17 136 642  paths for pairs with d = 2 17 82 257  paths for pairs with d = 3 33 244 1,025  paths sets for pairs with d = 1 680 13,633,830 887,805,286,368  paths sets for pairs with d = 2 680 1,749,060 8,984,340,696  paths sets for pairs with d = 3 5,456 144,084,501 9,336,731,022,080  total effort 195,608 17,839,699,137 3,234,134,601,579,840  approx. time 32 ms 23.1 min 8 years


## 2.1. The Fitness Function

We detail below the fitness function. As this is an interdisciplinary work, we express the fitness function mathematically (below) and also in a computational way in Algorithm2.Algorithm 2:Coloring fitness function.
function c o l o r i n g F i t n e s s ( c o l o r i n g ) r e s u l t ← 1 forEach vertex pair a in the Graphdo r ← p a i r F i t n e s s ( a , c o l o r i n g ) r e s u l t ← r e s u l t ∗ r  ⊳ Accumulate the product return result function p a i r F i t n e s s a , c o l o r i n g r e s u l t ← 0 forEach InternallyDisjointPathsSet DPSk of pair ado r ← d p s F i t n e s s ( D P S k , c o l o r i n g ) if r > r e s u l t then r e s u l t ← r  ⊳ Select best fitness return result function d p s F i t n e s s ( D P S k , c o l o r i n g ) r e s u l t ← 1 forEach Path p in DPSkdo r ← p a t h F i t n e s s ( p , c o l o r i n g ) r e s u l t ← r e s u l t ∗ r  ⊳ Accumulate the product return result function p a t h F i t n e s s ( p , c o l o r i n g ) r e s u l t ← p a t h N u m C o l o r s ( p , c o l o r i n g ) / p a t h . s i z e return result function p a t h N u m C o l o r s ( p , c o l o r i n g ) c o u n t ← 0 forEach Step s in pdo c ← c o l o r i n g [ s . s o u r c e ] [ s . d e s t ] ifnot used[c]then⊳ count colors only once c o u n t ← c o u n t + 1 u s e d [ c ] ← t r u e  ⊳ mark color as already used return countLetG be a graph, let Ψ(G) be the set of all possible colorings of the edges E(G), and let A be the set of all pairs of vertices of G, that is, A=a1,a2∣a1,a2∈V(G). The fitness function to be maximized using the RankGA is given as(3)coloringFitness:ΨG→R0,1(4)coloringFitnessψ=∏a∈ApairFitnessa,ψ1/Awhere ψ∈Ψ(G) and(5)pairFitness:A×ΨG→R0,1(6)pairFitnessa,ψ=maxPak∈DPSka⁡dpsFitnessPak,ψwhere DPSk(a) is the set of all sets Pak of k internally disjoint paths between the vertices in a and(7)dpsFitness:DPSka×ΨG→R0,1(8)dpsFitnessPak,ψ=∏p∈PakpathFitnessp,ψ1/Pakwhere(9)pathFitness:Pak×ΨG→R0,1(10)pathFitnessp,ψ=pathNumColorsp,ψEpwhere E(p) is the set of all edges in path p and(11)pathNumColors:Pak×ΨG→R0,1(12)pathNumColorsp,ψ=⋃e∈Epψewhere ψ(e) is the color that the coloring ψ assigns to edge e.The functionpathNumColors, in (12), calculates the cardinality of a set made out of the colors ψ(e) assigned to the edges e∈E(p) in path p. The function pathFitness, in (10), calculates the ratio of the pathNumColors over the length of path p, being this a value in the range 1/Ep,1, yielding 1 only in case the path has a rainbow coloring and lower values as the number of colors used in the path is reduced. The function dpsFitness, in (8), calculates the geometric mean of all the pathFitness values of all the k+1 paths p in the disjoint path set Pak, yielding a value in the range [0,1] with 1 representing a rainbow disjoint path set. The function pairFitness, in (6), returns the maximum dpsFitness that can be obtained from the set of disjoint path sets DPSk(a) between the vertices in the vertex pair a yielding 1 if and only if there existsat least one rainbow disjoint path set Pak in DPSk(a). Finally, the function coloringFitness in (4) computes the geometric mean of all the pairFitness values yielding a result that is 1 if and only if all pairs of vertices a have a fitness value of 1; i.e., the given coloring ψ is a rainbow coloring.The pseudocode of the fitness function is given in Algorithm2.


## 2.2. Finding the Set of Internally Disjoint Paths Sets between Pairs of Vertices in a Graph

The total number of possible setsPak of k paths (internally disjoint or not) between the vertices in pair a is very high as k grows so in order to save computing time when calculating the fitness of an individual, the function pairFitness in (6) iterates only on the elements of the set DPSk(a) which is the set of path sets Pak that contain k internally disjoint paths between the vertices in a. Algorithm 3 describes a way to calculate and store the set of all DPSk(a).Algorithm 3:Disjoint paths sets between vertices.
procedure s t o r e D i s j o i n t P a t h s S e t s G i n i t V e r t e x N e i g h b o r s  ⊳ set the neighbors of each vertex for current k forEach a∈A={{a1,a2}|a1,a2∈V(G)}do p a t h s [ a ] ← g e t P a t h s ( a , G , n u m C o l o r s ) d i s j o i n t P a t h s S e t s [ a ] ← g e t D i s j o i n t P a t h s S e t s ( p a t h s [ a ] , k ) function recursive g e t P a t h s ( a , G , m a x L e n g t h ) if m a x L e n g t h ≤ 0 then  ⊳ wrong length return null if v i s i t e d [ a 1 ] then  ⊳ a 1 has already been visited return null⊳ No paths to a2 if a 1 = a 2 then  ⊳ destination reached p ← { a 2 }  ⊳ single vertex in path return {p}⊳ single path in the set v i s i t e d [ a 1 ] ← t r u e for i = 1 to k+1do n e x t P a i r ← { n e i g h b o r [ i ] ( a 1 ) , a 2 }  ⊳ i t h neighbor of a1 s u b R e s u l t ← g e t P a t h s ( n e x t P a i r , G , m a x L e n g t h - 1 ) forEach path p in subResultdo n e w P a t h ← { a 1 } ⌢ p  ⊳ concatenate paths r e s u l t ← r e s u l t ∪ n e w P a t h  ⊳ aggregate path v i s i t e d [ a 1 ] ← f a l s e return result function g e t D i s j o i n t P a t h s S e t s ( P a , k ) forEach path set Pak of k paths p∈Pado⊳ may have huge # of iterations v i s i t e d ← f a l s e forEach internal vertex v of pdo if v i s i t e d [ v ] then next Pak v i s i t e d [ v ] ← t r u e r e s u l t ← r e s u l t ∪ P a k return resultIn this algorithm, the procedurestoreDisjointPathsSets takes each vertex pair a in G and calls function getPaths in order to get the full set Pa of paths p between the vertices in a with length l≤numColors (since longer paths cannot be rainbow colored). Then it calls another function getDisjointPathsSets which tests each set Pak containing k paths p∈Pa between the vertices in a to see if Pak is a disjoint paths set and returns the set DPSk(a) of disjoint paths sets Pak.The functiongetPaths is recursive and takes 3 parameters: a vertex pair a=a1,a2, a graph G, and a maximum length maxLength of the paths to be found. Figure 1 illustrates how this function works. Paths that go from vertex a1 to vertex a2 are made by adding the step from a1 to neighbori of a1 to all paths that go from neighbori of a1 to a2 for each i. But before doing this, vertex a1 is marked as visited in order to avoid paths that visit a vertex more than once. After computing the set of paths, vertex a1 is unmarked.Figure 1
Recursive finding of the set of paths between verticesa1 and a2.In Table2 we show how several measures grow with parameter k. First there is the number of vertices |V(G)| in the (k;6) cage followed by the total number of vertex pairs. Then there is the number of vertex pairs with distances d=1, d=2, and d=3 between them, respectively. We can see how the total number of paths with length l≤7=numColors between vertex pairs changes with distance d and with k. The next measure is the important one because it shows the drastic increase with k of the total number of paths sets containing k paths (internally disjoint and noninternally disjoint) that can be formed with the paths between the pairs of vertices with distances d=1, d=2, and d=3 between them, respectively. All these sets need to be tested to see which of them are disjoint pats sets. Finally we show the total number of paths sets that need to be tested and the approximate time to compute this with our existing algorithms and computing power. As one can see the numbers are much bigger as k increases making it practically impossible, at the moment, to do the work for k=5.Table 2
Growth withk of the effort to find the sets of disjoint paths sets.
k 3 4 5  VG 14 26 42  vertex pairs 91 325 861  vertex pairs with d = 1 21 52 105  vertex pairs with d = 2 42 156 420  vertex pairs with d = 3 28 117 336  paths for pairs with d = 1 17 136 642  paths for pairs with d = 2 17 82 257  paths for pairs with d = 3 33 244 1,025  paths sets for pairs with d = 1 680 13,633,830 887,805,286,368  paths sets for pairs with d = 2 680 1,749,060 8,984,340,696  paths sets for pairs with d = 3 5,456 144,084,501 9,336,731,022,080  total effort 195,608 17,839,699,137 3,234,134,601,579,840  approx. time 32 ms 23.1 min 8 years


## 3. Results

The genetic algorithm was able to find several rainbow colorings of the(k;6)-Moore cage for k=3 and k=4 using 7 colors. Using 6 colors, the algorithm could not find any rainbow colorations for neither k=3 nor k=4. A sample rainbow coloring that was found can be seen in Figure 2.Figure 2
Sample rainbow coloring withk=4 and numColors=7.


## 4. Conclusions

The problem of finding the rainbowk-connectivity rct(G) of (k;6)-cages is intractable by exhaustive search. So it had not been possible to verify if it is possible to improve the upper bound given by (2). With the Rank GA we could see that it is unlikely that the upper bound for (3;6)-cages is less than 7, since with 6 colors no solution was found after having let the algorithm run for a long time. We also found that for the (4;6)-cage there is an upper bound of 7 colors since the algorithm found rainbow colorings in this case. This upper bound improves quite a lot the 13 colors given by (2) which binds the rainbow k-connectivity of (k;6)-cages with a quadratic function. By finding out that the upper bound for the (4;6)-cage is 7 we know that this upper bound function could be one that grows slower than a quadratic function and may be much slower. To find the form of this function the problem should be scaled to Moore cages with k≥5; however, for k=5, the problem is computationally very expensive, with the algorithms and computing power that we currently use. Thus, as for future work we will consider different approaches such as taking into account the symmetries of the graph, parallelization, and improvement of algorithms.We believe that graph theory can benefit from the use of artificial intelligence techniques in some known NP-Complete and NP-Hard problems such as the one presented in this paper and there may be many of these cases.



---

*Source: 4073905-2019-03-03.xml*