On stratification and domination in graphs
Ralucca Gera, Ping Zhang · Discussiones Mathematicae Graph Theory · 2006
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 Fdomination number γ F (G) is the minimum number of red vertices in an F -coloring of G.In this paper, we study F -domination, where F is a 2-stratified red-blue-blue path of order 3 rooted at a blue end-vertex.We present characterizations of connected graphs of order n with Fdomination number n or 1 and establish several realization results on F -domination number and other domination parameters.