Computing graph invariants on rotagraphs using dynamic algorithm approach: the case of (2,1)-colorings and independence numbers Original Research Article

Rotagraphs generalize all standard products of graphs in which one factor is a cycle. A computer-based approach for searching graph invariants on rotagraphs is proposed and two of its applications are presented. First, the λ-numbers of the Cartesian product of a cycle and a path are computed, where the λ-number of a graph G is the minimum number of colors needed in a (2,1)-coloring of G. The independence numbers of the family of the strong product graphs C7⊠C7⊠C2k+1 are also obtained.