Domination number and neighbourhood conditions

Beifang Chen, Sanming Zhou*

*Corresponding author for this work

Research output: Contribution to journalJournal Articlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)81-91
Number of pages11
JournalDiscrete Mathematics
Volume195
Issue number1-3
DOIs
Publication statusPublished - 1999

Fingerprint

Dive into the research topics of 'Domination number and neighbourhood conditions'. Together they form a unique fingerprint.

Cite this