## Abstract

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 language | English |
---|---|

Pages (from-to) | 11-18 |

Number of pages | 8 |

Journal | Ars Combinatoria |

Volume | 80 |

Publication status | Published - Jul 2006 |

Externally published | Yes |

## Keywords

- External private neighbor
- Private dominating set
- Private neighbor

## ASJC Scopus subject areas

- General Mathematics