Path algebra and domination problems on graph products

Using algebraic approach we show that different domination problems on the class of polygraphs can be solved in constant time. As polygraphs include products of paths and cycles, we implement the algorithm to get some closed expressions for the domination, the independent domination and the Roman domination number of the Cartesian and the direct product of paths and cycles, where the size of one factor is fixed. Additionally we show that the values of the investigated graph invariants on the fasciagraphs and the rotagraphs with the same monograph can only differ for a constant value.

This is a joint work with Janez Žerovnik.

The slides from the talk are available here: DOWNLOAD SLIDES!