A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on *γ*_{t} (P_{k} □ P_{m})

ABSTRACT

Gravier *et
al*. established bounds on the size of a minimal totally dominant subset for graphs *P*_{k}□_{}*P*_{m}. 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=P*_{k}_{}□*H*. 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 *P*_{k}_{}□_{ }*C*_{n} when *k* and *n* satisfy specific modular conditions. Bounds
for *r*_{t}*(P*_{k}□*P*_{m}) , 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*γ*_{t} (P_{k} □ P_{m})," *Open Journal of Discrete Mathematics*, Vol. 3 No. 4, 2013, pp. 175-182. doi: 10.4236/ojdm.2013.34031.

P. Feit, "A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on

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

[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