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.