Connected p-domination in graphs

Abstract

We consider finite graphs G with vertex set V(G). By n(G) = |V(G)| and δ(G) we denote the order and the minimum degree of G., respectively. Let p be a positive integer. A subset D ⊆ V (G) is a p-dominating set of the graph G., if every vertex υ ∈ V(G) - D is adjacent to at least p vertices in D. The p-domination number γ_p(G) is the minimum cardinality among the p-dominating sets of G.A. subset D ⊆ V(G) is a connected p-dominating set of a connected graph G., if D is a p-dominating set of G and the subgraph induced by the vertex set D is connected. The connected p-domination number γ^c_p(G) is the minimum cardinality among the connected p-dominating sets of G. In this paper we characterize connected graphs G with γ^c_p(G) = n(G). In the case that δ(G) ≥ p ≥ 2, we also characterize the family of connected graphs G with γ^c_p(G) = n(G) - 1. Furthermore, we present different bounds of γ^c_p(G) and some open problems.