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

摘要

Rotagraphs generalize all standard products of grpahs 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 C_7 C_7 C_(2k + 1) are also obtained.