Abstract
Let G = (V,E) be a graph and let S ⊆ V. The set S is a dominating set of G is every vertex of V - S is adjacent to a vertex of S. A vertex v of G is called S-perfect if |N[v]∩S| = 1 where N[v] denotes the closed neighborhood of v. The set S is defined to be a perfect neighborhood set of G if every vertex of G is S-perfect or adjacent with an S-perfect vertex. We prove that for all graphs G, Θ(G) = Γ(G) where Γ(G) is the maximum cardinality of a minimal dominating set of G and where Θ(G) is the maximum cardinality among all perfect neighborhood sets of G.
Original language | English |
---|---|
Pages (from-to) | 221-225 |
Number of pages | 5 |
Journal | Discrete Mathematics |
Volume | 199 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 28 Mar 1999 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics