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

Paul Feit^{*}

Show more

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.

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