Private domination trees

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


For a subset of vertices S in a graph G, if v ∈ S and w ∈ V - S, then the vertex w is an external private neighbor of v (with respect to S) if the only neighbor of w in S is v. A dominating set S is a private dominating set if each v ∈ S has an external private neighbor. Bollóbas and Cockayne (Graph theoretic parameters concerning domination, independence and irredundance. J. Graph Theory 3 (1979) 241-250) showed that every graph without isolated vertices has a minimum dominating set which is also a private dominating set. We define a graph G to be a private domination graph if every minimum dominating set of G is a private dominating set. We give a constructive characterization of private domination trees.

Original languageEnglish
Pages (from-to)11-18
Number of pages8
JournalArs Combinatoria
Publication statusPublished - Jul 2006
Externally publishedYes


  • External private neighbor
  • Private dominating set
  • Private neighbor

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Private domination trees'. Together they form a unique fingerprint.

Cite this