Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič - Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs

dmtcs:3209 - Discrete Mathematics & Theoretical Computer Science, August 30, 2017, Vol. 19 no. 1 - https://doi.org/10.23638/DMTCS-19-1-25
Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphsArticle

Authors: Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič

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


    Volume: Vol. 19 no. 1
    Section: Graph Theory
    Published on: August 30, 2017
    Accepted on: August 2, 2017
    Submitted on: August 21, 2017
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 899 times.
    This article's PDF has been downloaded 556 times.