On well-dominated graphs
Preprint
Abstract
A graph is \emph{well-dominated} if all of its minimal dominating sets have the same cardinality. We prove that at least one of the factors is well-dominated if the Cartesian product of two graphs is well-dominated. In addition, we show that the Cartesian product of two connected, triangle-free graphs is well-dominated if and only if both graphs are complete graphs of order $2$. Under the assumption that at least one of the connected graphs $G$ or $H$ has no isolatable vertices, we prove that the direct product of $G$ and $H$ is well-dominated if and only if either $G=H=K_3$ or $G=K_2$ and $H$ is either the $4$-cycle or the corona of a connected graph. Furthermore, we show that the disjunctive product of two connected graphs is well-dominated if and only if one of the factors is a complete graph and the other factor has domination number at most $2$.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On Well-Covered Cartesian ProductsGraphs and Combinatorics, 2018
- Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphsDiscrete Mathematics & Theoretical Computer Science, 2017
- Well-dominated graphs without cycles of lengths andDiscrete Mathematics, 2017
- On the Cartesian Product of Non Well-Covered GraphsThe Electronic Journal of Combinatorics, 2013
- A revision and extension of results on 4-regular, 4-connected, claw-free graphsDiscrete Applied Mathematics, 2011
- Dominating direct products of graphsDiscrete Mathematics, 2007
- A Characterization of Well Covered Graphs of Girth 5 or GreaterJournal of Combinatorial Theory, Series B, 1993
- Domination‐balanced graphsJournal of Graph Theory, 1982
- Graph‐theoretic parameters concerning domination, independence, and irredundanceJournal of Graph Theory, 1979