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

DOI: 10.4236/ojdm.2013.34031   PDF   HTML     3,896 Downloads   6,165 Views  

Abstract

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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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 © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

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