On well-dominated direct, Cartesian and strong product graphs

DOI10.1016/J.DISC.2022.113178MaRDI QIDQ2092407zbMATH OpenOpenAlexFDO

Authors Douglas F. Rall

Publication date 2 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

direct productstrong productCartesian productwell-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: If each minimal dominating set in a graph is a minimum dominating set, then the graph is called well-dominated. Since the seminal paper on well-dominated graphs appeared in 1988, the structure of well-dominated graphs from several restricted classes have been studied. In this paper we give a complete characterization of nontrivial direct products that are well-dominated. We prove that if a strong product is well-dominated, then both of its factors are well-dominated. When one of the factors of a strong product is a complete graph, the other factor being well-dominated is also a sufficient condition for the product to be well-dominated. Our main result gives a complete characterization of well-dominated Cartesian products in which at least one of the factors is a complete graph. In addition, we conjecture that this result is actually a complete characterization of the class of nontrivial, well-dominated Cartesian products.

Recommendations

• On well-dominated graphs
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• scientific article; zbMATH DE number 4063149
• On well-edge-dominated graphs
• On unique minimum dominating sets in some Cartesian product graphs

Cites work

• scientific article; zbMATH DE number 4202288 (Why is no real title available?)
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• A revision and extension of results on 4-regular, 4-connected, claw-free graphs
• Associative graph products and their independence, domination and coloring numbers
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Handbook of product graphs
• On well-covered Cartesian products
• On well-dominated graphs
• Triangulations and equality in the domination chain
• Well covered simplicial, chordal, and circular arc graphs

Cited in

(7)

• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• On well-dominated graphs
• On well-edge-dominated graphs
• Boundary-type sets of strong product of directed graphs
• Exact vertex forwarding index of the strong product of complete graph and cycle
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• A characterization of well-dominated Cartesian products

This page was built for publication: On well-dominated direct, Cartesian and strong product graphs

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