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

dmtcs:3865 - Discrete Mathematics & Theoretical Computer Science, August 30, 2017, Vol 19 no. 1
Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs

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

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


Share

Browsing statistics

This page has been seen 73 times.
This article's PDF has been downloaded 33 times.