A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on <i>&#947_t (P_k □ P_m)</i>

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.