TY - JOUR
T1 - Domination number and neighbourhood conditions
AU - Chen, Beifang
AU - Zhou, Sanming
PY - 1999
Y1 - 1999
N2 - The domination number y 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 y which generalizes the known upper bound γ≤p + 1 -√2q + 1. Let 1(A) be the set of vertices adjacent to all vertices of A, and I(A) be the union of A and 1(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.
AB - The domination number y 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 y which generalizes the known upper bound γ≤p + 1 -√2q + 1. Let 1(A) be the set of vertices adjacent to all vertices of A, and I(A) be the union of A and 1(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.
UR - https://www.webofscience.com/wos/woscc/full-record/WOS:000077926100007
UR - https://openalex.org/W2059680011
UR - https://www.scopus.com/pages/publications/9344269370
U2 - 10.1016/S0012-365X(98)00166-6
DO - 10.1016/S0012-365X(98)00166-6
M3 - Journal Article
SN - 0012-365X
VL - 195
SP - 81
EP - 91
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -