On graphs with no proper perfect dominating set

Authors

  • Aseem Dalal

DOI:

https://doi.org/10.5556/j.tkjm.44.2013.975

Abstract

A set of vertices in a graph is perfect dominating if every vertex outside the set is adjacent to exactly one vertex in the set, and is neighborhood connected if the subgraph induced by its open neighborhood is connected. In any graph the full set of vertices is perfect dominating, and in every connected graph the full set of vertices is neighborhood connected. It is shown that(i) in a connected graph, if the only neighborhood connected perfect dominating set is the full set of vertices, then the full set of vertices is also the only perfect dominating set; and (ii) if $ r \ge 3 $ and $ n_1, \ldots ,n_r \ge 2 $, then in $K_{n_1,\ldots,n_r}$ the only perfect dominating set is the full set of vertices. Also, (iii) estimates are derived of how many edges can be removed from or added to $K_{n_1,\ldots ,n_r}$ while preserving the property described in (ii).

Author Biography

Aseem Dalal

Department ofMathematics, Indian Institute of Technology, Delhi-110016 , India.

References

S. Arumugam and C. Sivagnanam, Neighborhood connected domination in graphs, J. Combin. Math. Combin. Comput., 73 (2010), 55--64.

T. W. Haynes, S. T. Hedefniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc, New York, 1997.

P. Selvaraju, M. P. Kulaindaivel and C. Sivagnanam, Neighborhood connected perfect domination in graphs, Tamkang Journal Of Mathematics, 43 (2012), Number 4, 557--562., Winter 2012.

Downloads

Published

2013-12-30

How to Cite

Dalal, A. (2013). On graphs with no proper perfect dominating set. Tamkang Journal of Mathematics, 44(4), 359–364. https://doi.org/10.5556/j.tkjm.44.2013.975

Issue

Section

Papers