Title: Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs,
Abstract: A graph is said to be well-dominated if all its minimal dominating sets are
of the same size. The class of well-dominated graphs forms a subclass of the
well studied class of well-covered graphs. While the recognition problem for
the class of well-covered graphs is known to be co-NP-complete, the recognition
complexity of well-dominated graphs is open.
In this paper we introduce the notion of an irreducible dominating set, a
variant of dominating set generalizing both minimal dominating sets and minimal
total dominating sets. Based on this notion, we characterize the family of
minimal dominating sets in a lexicographic product of two graphs and derive a
characterization of the well-dominated lexicographic product graphs. As a side
result motivated by this study, we give a polynomially testable
characterization of well-dominated graphs with domination number two, and show,
more generally, that well-dominated graphs can be recognized in polynomial time
in any class of graphs with bounded domination number. Our results include a
characterization of dominating sets in lexicographic product graphs, which
generalizes the expression for the domination number of such graphs following
from works of Zhang et al. (2011) and of Šumenjak et al. (2012).