A parallel algorithm for generating ideal IC-colorings of cycles

作者：Liu Li Min^*

来源：Applied Mathematics and Computation, 2015, 250: 615-627.

DOI：10.1016/j.amc.2014.10.119

• IC-coloring
• Branch-and-bound
• Ideal IC-coloring
• IC-index

For a given graph G with the vertex set V(G), a coloring f : V(G) -> N produces alpha where alpha = Sigma(uV(H)) f(u) for some connected subgraph H of G (Sigma(uV(H)) f(u) = 0 if V(H) = empty set). The coloring f is an IC-coloring of G if f produces each alpha is an element of{0,1,...,S(f)}, where S(f) is the maximum number that can be produced by f. The IC-index M(G) of the graph G is the number max{S(g)vertical bar g is an IC-coloring of G}. An IC-coloring f is ideal if S(f) is equal to the number of connected subgraph of G. In this paper, a sound and complete parallel algorithm based on the branch and bound technique is proposed to generate ideal IC-colorings of cycles, C-n. Experiments identified 118 ideal IC-colorings of C-n when 2 < n < 20. Some cycles with particular length do not have any ideal IC-colorings while C-18 has the maximal 51 ideal IC-colorings. No pattern appeared among cycles with ideal IC-colorings, regarding the length of cycles.

• 出版日期2015-1-1