Stratified Claw Domination in Prisms

Gary Chartrand1, Teresa W. Haynes2, Michael A. Henning3, Ping Zhang4
1 Department of Mathematics and Statistics Western Michigan University Kalamazoo, MI 49008 USA
2Department of Mathematics East Tennessee State University Johnson City, TN 37614-0002 USA
3Department of Mathematics University of Natal, Private Bag X01 Pietermaritzburg, 3209 South Africa
4Department of Mathematics and Statistics Western Michigan University Kalamazoo, MI 49008 USA

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), where the vertices in one class are colored red and those in the other class are colored blue. Let \(F\) be a 2-stratified graph rooted at some blue vertex \(v\). An \(F\)-coloring of a graph is a red-blue coloring of the vertices of \(G\) in which every blue vertex \(v\) belongs to a copy of \(F\) rooted at \(v\). The \(F\)-domination number \(\gamma_F(G)\) is the minimum number of red vertices in an \(F\)-coloring of \(G\). In this paper, we determine the \(F\)-domination number of the prisms \(C_n \times K_2\) for all 2-stratified claws \(F\) rooted at a blue vertex.