Open Journal of Discrete Mathematics

Volume 3, Issue 4 (October 2013)

ISSN Print: 2161-7635   ISSN Online: 2161-7643

Google-based Impact Factor: 0.64  Citations  

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

HTML  Download Download as PDF (Size: 310KB)  PP. 175-182  
DOI: 10.4236/ojdm.2013.34031    4,293 Downloads   6,926 Views  Citations
Author(s)

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.

Cited by

No relevant information.

Copyright © 2024 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.