OJDM  Vol.3 No.4 , October 2013
A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on &#947t (Pk □ Pm)
Author(s) Paul Feit*
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.


Cite this paper
P. Feit, "A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on &#947t (Pk □ Pm)," Open Journal of Discrete Mathematics, Vol. 3 No. 4, 2013, pp. 175-182. doi: 10.4236/ojdm.2013.34031.
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

 
 
Top