Domination number and neighbourhood conditions Original Research Article

The domination number γ of a graph G is the minimum cardinality of a subset D of vertices of G such that each vertex outside D is adjacent to at least one vertex in D. For any subset A of the vertex set of G, let ∂+(A) be the set of vertices not in A which are adjacent to at least one vertex in A. Let N(A) be the union of A and ∂+(A), and d(A) be the sum of degrees of all the vertices of A. In this paper we prove the inequality 2q ⩽ (p−γ)(p−γ+2)−|∂+(A)| (p−γ+1)+d(N(A)), and characterize the extremal graphs for which the equality holds, where p and q are the numbers of vertices and edges of G, respectively. From this we then get an upper bound for γ which generalizes the known upper bound γ⩽p+1−2q+1. Let I(A) be the set of vertices adjacent to all vertices of A, and I(A) be the union of A and I(A). We prove that 2q ⩽ (p − γ − |I(A)| + 2)(p − γ + 4) + d(I(A)) − min{p − γ − |I(A)| + 2, |A|, |I(A)|, 3}, which implies an upper bound for γ as well.