On well-dominated direct, Cartesian and strong product graphs

DOI10.1016/J.DISC.2022.113178zbMATH Open1502.05215arXiv2105.09797OpenAlexW3161846043MaRDI QIDQ2092407FDOQ2092407

Authors: Douglas F. Rall 

Publication date: 2 November 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• On well-dominated graphs
• On well-edge-dominated graphs
• Exact vertex forwarding index of the strong product of complete graph and cycle
• Boundary-type sets of strong product of directed graphs
• 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)