On well-dominated graphs

DOI10.1007/S00373-020-02235-ZMaRDI QIDQ2657074zbMATH OpenOpenAlexFDO

Authors Sarah E. Anderson, Kirsti Kuenzel, Douglas F. Rall

Publication date 17 March 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.09955

zbMATH Keywords

Cartesian productdirect productdisjunctive productwell-coveredwell-dominated

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

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$.

Recommendations

• On well-dominated direct, Cartesian and strong product graphs
• On well-edge-dominated graphs
• scientific article; zbMATH DE number 4063149
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• On well-covered direct products

Cites work

• A characterization of well covered graphs of girth 5 or greater
• A revision and extension of results on 4-regular, 4-connected, claw-free graphs
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• Dominating direct products of graphs
• Domination-balanced graphs
• Graph-theoretic parameters concerning domination, independence, and irredundance
• scientific article; zbMATH DE number 4202288 (Why is no real title available?)
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• scientific article; zbMATH DE number 68351 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the Cartesian product of non well-covered graphs
• On well-covered Cartesian products
• Some covering concepts in graphs
• Well-dominated graphs without cycles of lengths 4 and 5

Cited in

(11)

• On well-dominated direct, Cartesian and strong product graphs
• On well-edge-dominated graphs
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• Recognizing well-dominated graphs is coNP-complete
• A characterization of well-dominated Cartesian products
• Well-forced graphs
• Well-failed graphs
• On well (edge) dominated and equimatchable strong product graphs
• Eulerian k-dominating reconfiguration graphs
• Well paired-dominated graphs

This page was built for publication: On well-dominated graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2657074)