Printer Friendly

Classification of distance-regular graphs and application of ant colony algorithm in three regular graph coloring.

1. Introduction

Put forward by the British mathematician N. L. Biggs in the 1970s, the concept of distanceregular graph is a mix derivative of distance-transitive graphs. (G. M. Adel'son-Vel'skii et al., 1969). Got the first example of distance intransitivity distance-regular graphs, and the distance-regular graph with the smallest distance intransitivity is Shrikhande Figure (S. S. Shrikhande., 1959).

The classification of distance-regular graphs is one of the core problems in the research of distance-regular graphs. (T.Ito, N.L.Biggs and A.G.Boshier., 1989) completed the classification of Dgree-3 distance-regular graphs in the 1980s; in 2000, (A.Hiraki, Suzuki et al., 2000) completed the classification of distance-regular graphs with and [a.sub.1] = 1, and failed to find a satisfactory solution to the classification of those with k [greater than or equal to] 7 and [a.sub.1] > 1; in 2002, (A. E. Brouwer and J.Koolen., 2002) improved the results obtained by (E. Bannai and T.Ito., 1989), and classified Degree-4 distance-regular graphs with the help of computer . In 2008, (Zhang Yuan., 2008) pointed out that when k = 8, and [c.sub.r+1], > 1, the distance-regular graphs with d = r + 1 don't exist. In this paper, the distance-regular graphs with k = 10, [a.sub.1] = 1 is studied and characterized, with the purpose of making some contribution to the improvement of the theory on distanceregular graphs.

Graph coloring is actually the process of classifying some objects according to certain rules, thus it is of large application significance in both theory and engineering practices. As an NPC problem, graph coloring doesn't involve exact algorithms of polynomial time (Lindo-Salado-Echeverria, C., Sanz-Angulo, P., De-Benito-Martin, J. J., & Galindo-Melero, J., 2015), and therefore the solving algorithm for it has become a hot research topic. Some achievements in graph coloring have currently been made at home and abroad by employing some intelligent algorithm models, such as taboo search, simulated annealing and genetic algorithm (Salari E, Eshghi., 2008; E. Bannai and T. Ito., 1987). The ant colony algorithm, which is a bionic algorithm, is applied herein to the study of the three regular graph coloring problem, in order to gain a more reasonable solution to the problems of coloring and number labeling.

2. Discussion about Existence of Distance-regular Graphs

2.1. Existence Theorem

Theorem 1: Supposed that [GAMMA] is a distance-regular graph with k = 10, [a.sub.1] = 1, it is set that [c.sub.r+1] = 4, then: [a.sub.r+1] = 4, d = r + s +1 and [c.sub.d] = 5, thus in this case [GAMMA] is a 1-homogeneous graph; when [c.sub.r+1] = 3, [GAMMA] does not exist (Van Dam E R, Haemers W H., 2003).

Supposed that [GAMMA] = (X,E) is a graph and u [member of] [GAMMA], then:

[GAMMA].sub.i] (u) = {v [member of] [gamma]|[[partial derivative].sub.[GAMMA]] (u, v) = i} and [GAMMA] (u) = [[GAMMA].sub.1] (u)

Definition 1: It is supposed that [GAMMA] = (X, E) is a connected graph, wherein X is a vertex set and E is a side set. Two random points u,v are extracted randomly and [partial derivative](u,v) = h. If [absolute value of [[GAMMA].sub.i] (u) [intersection] [[GAMMA].sub.j] (v)] is only related to h,i, j and not related to the selection of u,v, then [GAMMA] is a distance-regular graph.

The basics of distance-regular graphs, including the number of crosses and cross table, are presented in Reference (Tommy R, Jensen, Bjarne Toft. 1994).

Proposition 2: Supposed that [GAMMA] is a distance-regular graph with a diameter of d, for each side [omega] of [GAMMA], [D.sup.1.sub.1] (u,v) is the cluster, then [GAMMA] is a 1-homogeneous graph if and only if [a.sub.i] = [a.sub.1] x [c.sub.i] (i = 0, 1, ..., d).

2.2. Theorem Proving

It is supposed that [GAMMA] is a distance-regular graph with k = 10, [a.sub.1] = 1 considering that the graph [C.sub.r+1]--is a residual cluster and [c.sub.r+1] = 4, thus [a.sub.r+1] = 4, 5 or 6.

[a.sub.r+1] [not equal to] 5,6 should be proved to obtain the theorem conclusion (A. E. Brouwer, J. Koolen., 1996; Cranston D W, Kim S J., 2008).

Firstly, [a.sub.r+1] [not equal to] 6 is proved. And the following lemma is accordingly put forward:

Lemma 1: Supposed that [GAMMA] is the distance-regular graph with k = 10, a = 1, if [c.sub.r+1] = 4, then for any x [member of] [D.sup.r+1.sub.r+1], e(x,[D.sup.r.sub.r]) [less than or equal to] 1 stands. Particularly, when [a.sub.r+1] = 4, the equation stands, namely, [D.sup.r+1.sub.r+1] [subset] [[GAMMA].sub.r] ([gamma]).

Lemma 2: Supposed that [GAMMA] is the distance-regular graph with k = 10, [a.sub.1] = 1, if [c.sub.r+1] = 4, then [a.sub.r+1] [not equal to] 6.

Proving: (disproof) It is supposed that [a.sub.r+1] = 6, then d = r +1. Lemma 1 indicates that there is x [member of] [D.sup.r.sub.r] which makes e(x, [D.sup.r.sub.r]) = 0. Thus

[partial derivative](x,[gamma]) = d = r + 1. (1)

Given [c.sub.r+1] = 4, and supposed

{[[eta].sub.1], [[eta].sub.2], [[eta].sub.3], [[eta].sub.4]} = [GAMMA] (x) [intersection] [D.sup.r.sub.r+1] (2)

{[[eta].sub.5], [[eta].sub.6], [[eta].sub.7], [[eta].sub.8]} = [GAMMA] (x) [intersection] [D.sup.r+1.sub.r] (3)

[[eta].sub.1], [[eta].sub.2], [[eta].sub.3], [[eta].sub.4], [[eta].sub.5], [[eta].sub.6], [[eta].sub.7], [[eta].sub.8] [member of] [A.sub.r+1] ([gamma],x) (4)

Which contradicts with [a.sub.r+1] = 6.

Secondly, [a.sub.r+1] [not equal to] 5 is proved.

Supposed that [GAMMA] is the distance-regular graph with k = 10, [a.sub.1] = 1, [c.sub.r+1] = 4 is set. Supposed that [a.sub.r+1] = 5, each graph [C.sub.r+2]--would be the union of a number of [k.sub.2]; and given that each [C.sub.r+2]- graph contains a [C.sub.r+1]- graph, then, [c.sub.r+2] would be equal to 8 or 10. In order to prove that [c.sub.r+2] cannot be 8 or 10, the following lemmas are put forward:

Lemma 3: Supposed that [GAMMA] is the distance-regular graph with k = 10, [a.sub.1] = 1, if [b.sub.d-1] = 1 and [c.sub.d] = 8, then [k.sub.d] [equivalent to] 0(mod3).

Lemma 4: Supposed that [GAMMA] is the distance-regular graph with k = 10, [a.sub.1] = 1, if [a.sub.r+1] = 5 and d = r + 2, then [c.sub.r+2] [not equal to] 8.

Proving: Supposed that [c.sub.r+2] = 8, because d = r + 2 and [b.sub.r+1] = [b.sub.d-1] = 1, Lemma 3 indicates [k.sub.d] [equivalent to] 0([mod.sub.3]), which obviously contradicts with [k.sub.d] = (10 x [8.sup.r] x 1)/([1.sup.r] x 4 x 8).

Lemma 5: Supposed that [GAMMA] is the distance-regular graph with k = 10,[a.sub.1] = 1, if [c.sub.r+2] = 8, then [D.sup.r+1.sub.r+1] contains two and only two types of points, namely (1,0,1) and(1,2,1), each with one determined cluster model.

Proving: [a.sub.r+1] = 5 [not equal to] 0, so [D.sup.r+1.sub.r+1] [not equal to] [PHI]. Because there is no (1,1,1) point related to any side in [GAMMA], there is no (1,1,1) points in [D.sup.r+1.sub.r+1].

x [member of] [D.sup.r.sub.r] is taken randomly.

Because [b.sub.r] [not equal to] 0 and e([D.sup.r.sub.r], [D.sup.r.sub.r+1]) = e([D.sup.r.sub.r], [D.sup.r+1.sub.r]) = 0, there is y [member of] [D.sup.r+1.sub.r+1] which makes x ~ y, and obviously [??] = (1,0,1).

It is supposed that [D.sup.r+1.sub.r+1] does not contain (1,2,1) point, then.

e ([D.sup.r.sub.r], [D.sup.r+1.sub.r+1]) = [b.sub.r] x [absolute value of [D.sup.r.sub.r]] = [8.sup.r] (4)

which contradicts with e([D.sup.r.sub.r], [D.sup.r+1.sub.r+1]) = 1 x [absolute value of [D.sup.r+1.sub.r+1]] = 5* [8.sup.r]/4. Therefore [D.sup.r+1.sub.r+1] does contain (1,2,1) points.

[??] = (1,0,1) is taken, then e(x, [D.sup.r+2.sub.r+2]) = 0.

Because [b.sub.r+1] = 1, e(x, [D.sup.r+2.sub.r+2]) = e(x, [D.sup.r+2.sub.r+1]) = 1 can be obtained. Supposed that

{[u.sub.1]} = [GAMMA] (x) [intersection] [D.sup.r+1.sub.r+2] (5)

{[v.sub.1]} = [GAMMA] (x) [intersection] [D.sup.r+2.sub.r+1] (6)

[u.sub.1] and [v.sub.1] are apparently non-adjacent.

Because e(x, [D.sup.r.sub.r]) = 1, {x'} = [GAMMA] (x) [intersection] [D.sup.r.sub.r] is supposed. And because [c.sub.r+1] = 4

{[[eta].sub.1], [[eta].sub.2], [[eta].sub.3]} = [GAMMA] (x) [nersection] [D.sup.r.sub.r+1] (7)

{[[omega].sub.1], [[omega].sub.2], [[omega].sub.3]} = [GAMMA] (x) [intersection] [D.sup.r+1.sub.r] (8)

are supposed. Because [a.sub.r+1] = 5, {y} = [GAMMA] (x) [intersection] ([D.sup.r+1.sub.r+1], [D.sup.r+1.sub.r+1]) is supposed.

It is noticed that in [GAMMA] (x) = {x',y, [[eta].sub.1], [[eta].sub.2], [[eta].sub.3], [[omega].sub.1], [[omega].sub.2], [[omega].sub.3], [u.sub.1], [v.sub.1]}.

There is no sides existing between (1,0,1) points and (1,2,1) points, thus x' ~ y. Because

[[eta].sub.1]. [[eta].sub.2], [[eta].sub.3] [member of] [C.sub.r+1]([alpha], x) (9)

[[eta].sub.1], [[eta].sub.2], [[eta].sub.3] are mutually non-adjacent.

[[omega].sub.1], [[omega].sub.2], [[omega].sub.3] [member of] [C.sub.r+1] ([beta],x) (10)

so [[omega].sub.1], [[omega].sub.2], [[omega].sub.3] are mutually non-adjacent, thus [u.sub.1] ~ [[eta].sub.1], [v.sub.1] ~ [[omega].sub.1], [[eta].sub.2] ~ [[omega].sub.2] and [[eta].sub.3] ~ [[omega].sub.3] are supposed, then the group model of (1,0,1) points are unique.

[??] = (1,2,1)is taken, and because [c.sub.r+1] = 4 and e(x,D) 0, {[[eta].sub.1], [[eta].sub.2], [[eta].sub.3], [[eta].sub.4]} = [GAMMA] (x) [intersection] [D.sup.r.sub.r+1] and {[[omega].sub.1], [[omega].sub.2], [[omega].sub.3], [[omega].sub.4]} = [GAMMA](x) [intersection] [D.sup.r+1.sub.r] are set. [b.sub.r+1] = 1 and [c.sub.r+2] = 8, so e(x,[D.sup.r+1.sub.r+2])) = e(x, [D.sup.r+2.sub.r+1])) = 0 and e (x, [D.sup.r+2.sub.r+2])) = 1, and {u} = [GAMMA] (x) [intersection] [D.sup.r+2.sub.r+2]) is set. Because [a.sub.r+1] = 5, {v} = [GAMMA](x) [intersection] [D.sup.r+1.sub.r+1] is set and in

[GAMMA] (x) = {[[eta].sub.1], [[eta].sub.2], [[eta].sub.3], [[eta].sub.4], [[omega].sub.1], [[omega].sub.2], [[omega].sub.3], [[omega].sub.4],u,v} u ~ v (11)

It is noticed that{[[eta].sub.1], [[eta].sub.2], [[eta].sub.3], [[eta].sub.4]} = [C.sub.r+1]([alpha],x), so [[eta].sub.1], [[eta].sub.2], [[eta].sub.3], [[eta].sub.4] are mutually non-adjacent; {[[omega].sub.1], [[omega].sub.2], [[omega].sub.3], [[omega].sub.4]} = [C.sub.r+1] ([beta],x), so [[omega].sub.1], [[omega].sub.2], [[omega].sub.3], [[omega].sub.4] are mutually non-adjacent. It is set that [[eta].sub.1] ~ [[omega].sub.1], [[eta].sub.2] ~ [[omega].sub.2], [[eta].sub.3] ~ [[omega].sub.3] and [[eta].sub.4] ~ [[omega].sub.4], thus the group model of (1,2,1) points is unique.

Lemma 6: Supposed that [GAMMA] is a distance-regular graph with k = 10, [a.sub.1] = 1, if [a.sub.r+1] = 5 and d [greater than or equal to] r + 3 , then [c.sub.r+2] [not equal to] 8.

Lemma 7: Supposed that [GAMMA] is a distance-regular graph with k = 10, [a.sub.1] = 1, [c.sub.r+1] = 4 is set. If [a.sub.r+1] = 5, then [c.sub.r+2] [not equal to] 10.

Proving: According to the proving of Lemma 5, [D.sup.r+1.sub.r+1] contains (1,0,1) points. Like the proving of [c.sub.r+2] [not equalto] 8, [c.sub.r+2] = 10 is supposed. A circle with a length of 2r + 3 can also be taken and the deduction leads to contradiction, thus [c.sub.r+2] [not equal to] 10.

Hence, [a.sub.r+1] [not equal to] 5 is proved.

Supposed that [GAMMA] is a distance-regular graph with k = 10, [a.sub.1] = 1, if

([c.sub.r+1], [a.sub.r+1], [b.sub.r+1]) = (4,4,2)

it can be asserted that each [C.sub.r+2]--graph is a redundant group. In fact, y [member of] [GAMMA] (x) [intersection] [[GAMMA].sub.r+2] (x) is set, then apparently x [member of] [C.sub.r+2] ([alpha], y). Because [a.sub.r+1] = 4,

{[x.sub.1] ,[x.sub.2] ,[x.sub.3] ,[x.sub.4]} = [GAMMA] (x) [intersection] [[GAMMA].sub.r+1] ([alpha]) (12)

can be set. For a random point z in [C.sub.r+2]([alpha], y) that is different from x, apparently z [not equal to] [x.sub.1] ,[x.sub.2] ,[x.sub.3] ,[x.sub.4] stands. Therefore x and z are not adjacent, indicating that [C.sub.r+2]--graph is redundant group.

[C.sub.r+2]--graph is redundant group, thus [c.sub.r+2] = 4 or 5.

If [c.sub.r+2] = 5, then d = r + 2, which is the conclusion in this paper.

If [c.sub.r+2] = 4, it can be asserted that [b.sub.r+1] = [b.sub.r+2]. In fact, because [C.sub.r+2]--graph is redundant group, for a random y [member of] [D.sup.r+1.sub.r+1], [partial derivative](y,[gamma]) = [c.sub.r+1]. And since [c.sub.r+1] = [c.sub.r+2] = 4 and y is arbitrary e([D.sup.r+2.sub.r+2], [D.sup.r+1.sub.r+2]) = e([D.sup.r+2.sub.r+2], [D.sup.r+1.sub.r+2]) = 0, thus [b.sub.r+1] = [b.sub.r+2].

Like the proving and recursion above, ([c.sub.r+1], [a.sub.r+1], br+1) = ([c.sub.r+2], [a.sub.r+2], [b.sub.r+2]) = ... = ([c.sub.d-1] ,[a.sub.d-1] ,[b.sub.d-1]) = (4,4,2) can be obtained, and [C.sub.d]--graph is a residual cluster. Furthermore, [c.sub.d] = 4 or 5 can be obtained.

e([D.sup.d.sub.d], [D.sup.d-1.sub.d]) = e([D.sup.d.sub.d], [D.sup.d.sub.d-1]) > 0, so [c.sub.d] [not equal to] 4 and [c.sub.d] = 5. At this time, [GAMMA] is a 1-homogeneous graph.

Supposed that [GAMMA] is a distance-regular graph with k = 10, [a.sub.1] = 1, [c.sub.r+1] [not equal to] 3 can be obtained according to inter nature of [k.sub.r+1] = 10 x [8.sup.r]/1 x [c.sub.r+1]. Hence, when [c.sub.r+1] = 3, [GAMMA] does not exist. 1

3. Research of Conditional Coloring Problem in Three Regular Graph based on Ant Colony Algorithm

3.1. Derivation of Problem

Is it set that k > 0,k [member of] Z , one normal k--coloring of Graph G = (V(G),E(G)) is c: V(G) [right arrow] {1,2, ..., k}, which satisfies c(u) [not equal to] c(v). As for any uv [member of] E(G), the minimum positive integer k which satisfies normal k--coloring is called as the color number of G and recorded as [chi] (G). The problem of graph coloring aims to obtain the color number of a graph. The model is described as follows (Liu Jiangyuan, Tian Qing., 2014; Liu Na. et al., 2011):

Target: minimum color types applied in coloring of the whole graph.

Constraint conditions: (1) each point is colored by only one color type; (2) previous colors are used preferentially; (3) different colors are used by two adjacent points; (4) colors with smaller numbers will be used more frequently.

Hence, the mathematical model of the graph coloring problem is as follows:


Where: h refers to a color number. [x.sub.ih] shows whether the h-th color is colored by the i-th point. [y.sub.h] shows whether the h-th color is used, wherein n = [absolute value of V (G)].

3.2. Design and Optimization of Ant Colony Algorithm for Graph Coloring

Ant colony optimization (ACO) is a probability-type algorithm used to find optimized routes in a graph. It was proposed by Marco Dorigo in his doctoral thesis during 1992, wherein its inspiration was derived from ants' route discovery during food search(Xiang Chang-sheng, Zhou Zi-ying. 2010). ACO is a simulated evolutionary algorithm. Preliminary researches show that the algorithm has many advantageous natures. ACO is an algorithm simulating random route search of ants(Xiang Chang-sheng, Zhou Ziying., 2010). An ant stays in a square grid. By setting ant parameters, speed and radius (assumed as 3), it can be observed that the ant can move in the square grid with scope of 3*3, wherein its moving or walking distance will not exceed the scope.


Environment refers to a virtual surrounding environment for moving of an ant. There are obstacles and other ants as well as pheromones left by the ant in its action environment. The pheromones are classified into two types: pheromones secreted for food search and pheromones secreted for search of ant nest. Pheromones of environmental factors around the ant disappear according at a certain rate.

Foraging Rules

The ant searches food within a near distance and can directly obtain the food after finding it. If the ant cannot find food within the sensing scope, it will conduct searching based on food pheromones. By comparing pheromone contents in different directions within the sensing scope, the ant can determine multiple directions of the pheromones and select them. The probability is small for an ant to make mistakes, so one direction determined by the ant may not be the location containing most pheromones.

Moving Rules

The ant begins moving in the direction with the most pheromones. However, when there is no pheromone around which can be taken as the judgment direction, the ant will carry out food search in the original moving direction. In addition, a small random disturbance will take place in the moving direction. The ant will remember the points passed by it. It will try to avoid the point as much as possible if it finds that the next point has been passed before.

Obstacle Avoidance Rules

In the face of obstacles encountered during moving, the ant will move according to pheromones under their guidance. Otherwise, it will select the direction randomly in order to bypass the obstacle. After that, the ant will change the next position under the pheromone guidance according to the foraging rules.

Pheromone Rules

The disseminated pheromones will gradually decrease along with the increase of ant moving distance. In addition, the ant will secrete the most pheromones when it finds food or nest. According to ant behaviors, there are no direct interactive relations among ants. Through interactions between pheromones and environment, all the ants are correlated in fact. When an ant finds food, it will release food pheromones to the surrounding environment rather than directly transmit the food position source to another ant. Other ants can determine direction and route for food search by judging pheromones around them in order to get the food position information indirectly from other ants.

Initial colored point and new colored points at each step are completely controlled by the transition probability randomly. There are 7 basic steps, as shown below:

STEP 1: Parameters are initialized. (Parameters include total quantity of ants, circulation times, adjacent matrix of graph and pheromone matrix.).

STEP 2: Usable color sets of all the points are set. The first node is taken as the initial colored point and colored by the first color. The usable color set for points adjacent to the first point is updated.

STEP 3: Transition probability from a colored point to each uncolored point is calculated. Each probability is multiplied by a random number. The point corresponding to the maximum value is taken as the next colored point. Pheromones are also updated.

STEP 4: The selected colored points are colored. Colors used in coloring can be selected from the usable color set. The usable color set of points adjacent to the colored point are updated.

STEP 5: If any uncolored point still exists, the STEP3 will be restarted.

STEP 6: The scheme applying the minimum color types in each round of iteration is selected. Corresponding results are stored, wherein NC = NC +1.

STEP 7: If NC [less than or equal to] NC _MAX, STEP2 will be restarted. Otherwise, the scheme with the minimum color number in each iteration is selected, and the algorithm is then ended.

Optimization of above algorithm is mainly realized at STEP2 and STEP3. At first, the first colored point selected at STEP2 is colored by the first color. Instead, the first point is selected randomly and colored by one color randomly. After that, the STEP3 is started. During pheromone updating, one maximum value is set initially. Updating of each step is controlled within a scope. Pheromones are updated only when the optimal solution is found in the current circulation. The updating formula is as follows:

[[tau].sub.ij] (t + 1) = (1 - [rho]) [[tau].sub.ij](t) + [DELTA] [[tau].sup.min.sub.ij], [DELTA][[tau].sup.min.sub.ij] = Q/min ([L.sub.k]) = (14)

Where: min ([L.sub.k]) refers to the current optimal solution of the iteration, namely the current minimum coloring number during the iteration. Q refers to a constant which represents the total quantity of information released during a circulation completed by the ant. [[tau].sub.ij] refers to the pheromone content from point i to point j. [rho] refers to a pheromone volatilization factor. If [[tau].sub.ij] [greater than or equal to] [[tau].sub.max] stands, [[tau].sub.ij] = [[tau].sub.max] will be set. If [[tau].sub.ij] [less than or equal to] [[tau].sub.max] stands, [[tau].sub.ij] = [[tau].sub.min] will be set. In the following formulas, P is a parameter constant and NC is the number of iterations.


The above algorithm is tested. In MATLAB, the graph is converted into an adjacent matrix. After that, according to algorithm programming, the random graph and the standard calculation example are respectively tested. The maximum number of iterations is set to be 100. The ant colony number is set to be 30. The pheromone volatilization factor is set to be 0.1. Weight of pheromones is set to be 10. Testing results of the obtained random graph are shown in Table 1.

Minimization of the used colors means that each independent color set [C.sub.i] shall contain as many points as possible. All the updated pheromones consider number of elements added into the color subset as a parameter. The updating formula is as follows:


3.3. Discussion of Conditional Coloring in Three Regular Graph based on Improved Ant Colony Algorithm

Conditional coloring of a three regular graph G can be converted into classical coloring of its square graph. According to results of Cranston and Kim [15], except for G which is a Petersen graph with [[chi].sub.r] (G) [less than or equal to] 8, the three regular graphs are tested. The three regular graphs, namely all the graphs with vertex degree of 3, are generated randomly at first. The algorithm of three regular graphs is generated as follows:

STEP 1: n unconnected points are generated. The first point is connected to other 3 random points.

STEP 2: If degree of the i-th point exceeds 3, the STEP1 will be restarted. Otherwise, the i-th point will be connected to several points from i+1 to n. The degree of i is set to be 3.

STEP 3: If i is not bigger than n, STEP2 will be restarted.

STEP 4: Whether the matrix is a three regular graph is determined. If the result is YES, results will be output and the step is ended; otherwise, STEP1 will be restarted.

When the adjacent matrix is obtained, it can be tested by the above graph coloring processes. Testing results are shown in Table 2:
Table 2--List of Testing Results of Three
Regular Graph Coloring Processes

                    Color number

Point     Maximum   Classical   Coloring under
number    degree    coloring    condition 3

10        3         3           5
20        3         3           6
30        3         3           6

          Calculation time (second)

Point     Classical   Coloring under
number    coloring    condition 3

10        0.515       0.813
20        1.172       3.344
30        2.156       6.516

4. Conclusions

Existence theorem of a distance-regular graph with k = 10, [a.sub.1] = 1 stands, which is proved in this paper from the theoretical level. The focused ant colony algorithm is a bionic algorithm. The algorithm is very applicable to overall optimal solution. It is highly applicable to graph conditional coloring problem after the improvement. The paper also applies MATLAB software to verify the testing programs. Results show that application effect of the improved ant colony algorithm in the three regular graph conditional coloring is better than classical coloring effect. In ant colony coloring algorithm, new colored points are selected randomly and dynamically in a reversed order according to coloring progress and degrees of points adjacent to uncolored points in order to equip the algorithm with strong ability to search overall optimal solutions. Solution quality of the ant colony coloring algorithm is improved. Its convergence rate is accelerated. Its excellent characteristics are also proved. Meanwhile, efficiency improvement of the algorithm also ensures that the algorithm can be applied to solution of large-scale coloring problems. In future researches, it is still necessary to research the methods for shortening operation time of ant colony algorithm.

Recebido/Submission: 10-09-2015

Aceitacao/Acceptance: 27-11-2015

DOI: 10.17013/risti.17A.313-323


Van Dam E R, Haemers W H. (2003). Which graphs are determined by their spectrum?. Linear Algebra and its applications, 373, 241-272.

A. E. Brouwer, J.Koolen, (1996). The distance-regular graph of valency four. Journal of Algebraic Combinatorics, 10, 5-24..

A. Hiraki, (1993). Circuit chasing technique in distance-regular with triangles, Europ. J. Combin. 14, 413-420.

A. Hiraki, (1995). Circuit chasing technique for a distance-regular graph with [c.sub.2r+1] = 1, Kyushu. J. Math, 49, 197-291.

A. Hiraki, K. Nomura and H. Suzuki, (2000). Distance-regular graphs of valency 6 and [a.sub.1] = 1, J. Alge. Combin. 11, 101-134.

Cranston D W, Kim S J. (2008). List-coloring the square of a sub-cubic graph. Journal of Graph Theory, 57, 65-87.

E. Bannai and T. Ito, (1987). On distance-regular graphs with fixed valency, Graphs and Combin, 3, 95-109.

E. Bannai and T. Ito, (1989). On distance-regular graphs with fixed valency, IV, European J. Combin, 10, 137-148.

G. M. Adel'son-Vel'skii, B. Ju. Veisfeiler, A.A. Leman, and I. A. (1969). Faradzev. Example of a graph without a transitive automorphism group, translated from the russian by m. l. Glasser. Soviet Math. Dokl. 10, 440-441.

Lindo-Salado-Echeverria, C., Sanz-Angulo, P., De-Benito-Martin, J. J., & Galindo-Melero, J. (2015). Aprendizaje del Lean Manufacturing mediante Minecraft: aplicacion a la herramienta 5S. RISTI--Revista Iberica de Sistemas e Tecnologias de Informacao, 2015(16), 60-75.

Liu Jiangyuan, Tian Qing. (2014). On the People's And Epochal Character of Nonmaterial Cultural Heritages--Taking the Tunes in YongNian Town and the Jin Drum in Cixian County as Examples. Net Friend World. 6, 23-30.

Liu Na, Yi Yuanzhong, Huang Xiaoyang, et al. (2011). Time Series Analysis on Bridge Deformation Monitoring Forecasting Based on Computer Prediction. Science of Surveying and Mapping. 36 (6), 65-73.

Malaguti E, Toth P. (2010). A survey on vertex coloring problems. International Transactions in Operational Research, 17, 1-34.

N. Yamazaki, (1995). Distence-regular graphs with [GAMMA](x) [congruent to] 3 x [K.sub.a+1] , Europ. J. Combin. 16, 525-536

S.S. Shrikhande. (1959). The uniqueness of the L2 association scheme. Ann. Math. Statist, 30, 781-798.

Salari E, Eshghi. (2008). An ACO algorithm for the graph coloring problem. Int. J. Contemp Math Sciences, 3(2008), 293-304.

Tommy R, Jensen, Bjarne Toft. (1994). Graph Coloring Problems. New York: Wiley-Interscience.

Xiang Chang-sheng, Zhou Zi-ying. (2010). Pest Multiple Dimension Time Series Forecasting Based on SVM. Application Research of Computers, 27 (10), 3694-3698.

Yuan Zhang. (2008). The Distance Regular Graphs with Order (2,3) and Even Geometric Girth. Shanghai Jiao Tong University, 55-67.

Junhong Ma (1) *, Yalou Liu (1), Qiumei Liu (1)


(1) College of science, North China University of Science and Technology, 063009, Tangshan, China.
Table 1--List of Testing Results of Random Graph

                                         Color number
                                         before improvement

Point     Maximum         Maximum        Ant      Maximum and
number    degree before   degree after   colony   minimum ant
          improvement     improvement             colonies

60        41              38             16       13
60        37              37             15       13
100       60              65             20       18
100       63              62             21       18
100       62              61             21       19

          Color number after      Calculation time
          improvement             before improvement

Point     Ant      Maximum        Ant      Maximum and
number    colony   and minimum    colony   minimum ant
                   ant colonies            colonies

60        14       13             16.313   10.109
60        13       15             17.657   10.344
100       19       19             62.094   36.859
100       19       19             64.547   37.485
100       19       19             61.703   37.696

          Calculation time
          after improvement

Point     Ant      Maximum and
number    colony   minimum ant

60        15.232   5.294
60        16.157   4.981
100       58.694   14.390
100       60.329   16.562
100       55.226   16.338
COPYRIGHT 2016 AISTI (Iberian Association for Information Systems and Technologies)
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ma, Junhong; Liu, Yalou; Liu, Qiumei
Publication:RISTI (Revista Iberica de Sistemas e Tecnologias de Informacao)
Date:Mar 15, 2016
Previous Article:Spatial analysis based analysis on landscape pattern of villages and towns and application of simulation.
Next Article:Research of multidimensional indexing in a cloud computing system.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters