Stratification and domination in graphs with minimum degree two Original Research Article

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 F be a 2-stratified graph with one fixed blue vertex image specified. We say that F is rooted at image. The F-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 image of G belongs to a copy of F rooted at image. We investigate the F-domination number when F is a 2-stratified path image on three vertices rooted at a blue vertex which is an end-vertex of the image and is adjacent to a blue vertex with the remaining vertex colored red. We show that for a connected graph of order n with minimum degree at least two this parameter is bounded above by image with the exception of five graphs (one each of orders four, five and six and two of order eight). For image, we characterize those graphs that achieve the upper bound of image.