On the super domination number of lexicographic product graphs
Preprint
Abstract
The neighbourhood of a vertex $v$ of a graph $G$ is the set $N(v)$ of all vertices adjacent to $v$ in $G$. For $D\subseteq V(G)$ we define $\overline{D}=V(G)\setminus D$. A set $D\subseteq V(G)$ is called a super dominating set if for every vertex $u\in \overline{D}$, there exists $v\in D$ such that $N(v)\cap \overline{D}=\{u\}$. The super domination number of $G$ is the minimum cardinality among all super dominating sets in $G$. In this article we obtain closed formulas and tight bounds for the super dominating number of lexicographic product graphs in terms of invariants of the factor graphs involved in the product. As a consequence of the study, we show that the problem of finding the super domination number of a graph is NP-Hard.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- On the (adjacency) metric dimension of corona and strong product graphs and their local variants: Combinatorial and computational resultsDiscrete Applied Mathematics, 2018
- Super Dominating Sets in GraphsProceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2015
- Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results2014
- Doubly connected domination in the corona and lexicographic product of graphsApplied Mathematical Sciences, 2014
- Rainbow domination in the lexicographic product of graphsDiscrete Applied Mathematics, 2013
- On the Roman domination in the lexicographic product of graphsDiscrete Applied Mathematics, 2012
- Associative graph products and their independence, domination and coloring numbersDiscussiones Mathematicae Graph Theory, 1996