Computing graph invariants on rotagraphs using dynamic algorithm approach: the case of (2,1)-colorings and independence numbers
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 are also obtained.
05c85 05c15 05c69 68r10