A characterization of well-dominated Cartesian products
Authors:
- Douglas F. RallDRDouglas F. Rall
Preprint
Abstract
A graph is well-dominated if all its minimal dominating sets have the same cardinality. In this paper we prove that at least one factor of every connected, well-dominated Cartesian product is a complete graph, which then allows us to give a complete characterization of the connected, well-dominated Cartesian products if both factors have order at least $2$. In particular, we show that $G\,\Box\,H$ is well-dominated if and only if $G\,\Box\,H = P_3 \,\Box\,K_3$ or $G\,\Box\,H= K_n \,\Box\,K_n$ for some $n\ge 2$.
Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphsDiscrete Mathematics & Theoretical Computer Science, 2017
- On the Cartesian Product of Non Well-Covered GraphsThe Electronic Journal of Combinatorics, 2013
- Graph‐theoretic parameters concerning domination, independence, and irredundanceJournal of Graph Theory, 1979