More on the super domination number of graphs
Preprint
Abstract
Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $S\subseteq V$ such that every vertex in $ V \setminus S$ is adjacent to at least one vertex in $S$. A dominating set $S$ is called a super dominating set of $G$, if for every vertex $u\in \overline{S}=V \setminus S$, there exists a $v\in S$ such that $N(v)\cap \overline{S}=\{u\}$. The cardinality of a minimum size super dominating set of $G$ is the super domination number of $G$. The problem of finding the super domination number of a graph is $\mathcal{NP}$-hard. In this paper, we continue the study of the super domination number of graphs and present tight bounds for neighbourhood corona product, $r$-gluing, and Haj\'{o}s sum of two graphs. We present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Super Domination in TreesGraphs and Combinatorics, 2021
- On the super domination number of lexicographic product graphsDiscrete Applied Mathematics, 2019
- Super domination number of unicyclic graphsIOP Conference Series: Earth and Environmental Science, 2019
- More on the total dominator chromatic number of a graphJournal of Information and Optimization Sciences, 2019
- On the Laplacian spectra of some variants of coronaLinear Algebra and its Applications, 2017
- Double domination and super domination in treesDiscrete Mathematics, Algorithms and Applications, 2016
- Bounds on the maximum number of minimum dominating setsDiscrete Mathematics, 2016
- Super Dominating Sets in GraphsProceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2015
- Spectra of the neighbourhood corona of two graphsLinear and Multilinear Algebra, 2013
- A fast algorithm to generate necklaces with fixed contentTheoretical Computer Science, 2003