Simultaneous stratification and domination in graphs with minimum degree two

Abstract

In this paper we continue the study of stratification and domination in graphs explored by Chartrand et al. in [4]. We define an F-coloring of a graph to be a red-blue coloring of the vertices such that every blue vertex is adjacent to a blue vertex and to a red vertex, with the red vertex itself adjacent to some other red vertex. The F-domination number γF(G) of a graph G is the minimum number of red vertices of G in an F-coloring of G. Let G be a connected graph of order n ≥ 4 with minimum degree at least 2. We prove that (i) if G has maximum degree Δ where Δ ≤ n − 2, then γF(G) ≤ n − Δ + 1, and (ii) if G ≠= C₇, then γF(G) ≤ 2n/3.

Keywords: 2-stratified graphs, domination, restrained domination, total domination

Quaestiones Mathematicae 29(2006), 313–328