Stratification and Domination in Prisms

Abstract

A graph $G$ is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let $X$ be a 2-stratified graph with one fixed blue vertex $v$ specified. We say that $X$ is rooted at $v$. The $X$-domination number of a graph $G$ is the minimum number of red vertices of $G$ in a red-blue coloring of the vertices of $G$ such that every blue vertex $uv$ of $G$ belongs to a copy of $X$ rooted at $v$. In this paper we investigate the $X$-domination number of prisms when $X$ is a 2-stratified 4-cycle rooted at a blue vertex.