On perfect neighborhood sets in graphs

Gerd H. Fricke, Teresa W. Haynes, Sandra Hedetniemi, Stephen T. Hedetniemi, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)221-225
Number of pages5
JournalDiscrete Mathematics
Volume199
Issue number1-3
DOIs
Publication statusPublished - 28 Mar 1999
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On perfect neighborhood sets in graphs'. Together they form a unique fingerprint.

Cite this