Share This Article:

A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on γt (Pk □ Pm)

Abstract Full-Text HTML Download as PDF (Size:310KB) PP. 175-182
DOI: 10.4236/ojdm.2013.34031    3,673 Downloads   5,902 Views
Author(s)    Leave a comment

Gravier et al. established bounds on the size of a minimal totally dominant subset for graphs PkPm. This paper offers an alternative calculation, based on the following lemma: Let so k≥3 and r≥2. Let H be an r-regular finite graph, and put G=PkH. 1) If a perfect totally dominant subset exists for G, then it is minimal; 2) If r＞2 and a perfect totally dominant subset exists for G, then every minimal totally dominant subset of G must be perfect. Perfect dominant subsets exist for Pk Cn when k and n satisfy specific modular conditions. Bounds for rt(PkPm) , for all k,m follow easily from this lemma. Note: The analogue to this result, in which we replace totally dominant by simply dominant, is also true.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

P. Feit, "A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on γt (Pk □ Pm)," Open Journal of Discrete Mathematics, Vol. 3 No. 4, 2013, pp. 175-182. doi: 10.4236/ojdm.2013.34031.

 [1] S. Gravier, “Total Domination of Grid Graphs,” Discrete Applied Mathematics, Vol. 121, No. 1-3, 2002, pp. 119-128. .http://dx.doi.org/10.1016/S0166-218X(01)00297-9 [2] S. Gravier, M. Molland and C. Payan, “Variations on Tilings in Manhattan Metric,” Geometriae Dedicata, Vol. 76, No. 3, 1999, pp. 265-273.http://dx.doi.org/10.1023/A:1005106901394

comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.