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 \v{S}umenjak et al. (2012).

Source : oai:arXiv.org:1701.05886

DOI : 10.23638/DMTCS-19-1-25

Volume: Vol. 19 no. 1

Section: Graph Theory

Published on: August 30, 2017

Submitted on: August 21, 2017

Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

This page has been seen 364 times.

This article's PDF has been downloaded 175 times.