Characterization of unicyclic graphs with equal 2-domination number and domination number plus one

Abstract

Let G be a simple graph, and let p be a positive integer. A subset D ⊆ V(G) is a p-dominating set of the graph G, if every vertex v ∈ V(G) - D is adjacent to at least p vertices of D. The p-domination number _γp(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number _γ1(G) is the usual domination number _γ(G). If G is a connected unicyclic graph, then we show that either _γ2(G) ≥ γ(G) + 1 or G = C₄, and we characterize all connected unicyclic graphs with _γ2(G) = _γ(G) + 1.