A1 Refereed original research article in a scientific journal
Super domination: Graph classes, products and enumeration
Authors: Ghanbari Nima, Jäger Gerold, Lehtilä Tuomo
Publisher: Elsevier
Publication year: 2024
Journal: Discrete Applied Mathematics
Journal name in source: Discrete Applied Mathematics
Volume: 349
First page : 8
Last page: 24
ISSN: 0166-218X
eISSN: 1872-6771
DOI: https://doi.org/10.1016/j.dam.2024.01.039
Web address : https://doi.org/10.1016/j.dam.2024.01.039
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/386892683
Preprint address: https://arxiv.org/abs/2209.01795
The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given graph G=(V,E), a dominating set of G is a subset S⊆V such that every vertex in V∖S is adjacent to at least one vertex in S. Furthermore, the DSP is the problem of finding a minimum-size dominating set and the corresponding minimum size, the domination number of G. In this, work we investigate a variant of the DSP, the super dominating set problem (SDSP), which has attracted much attention during the last years. A dominating set S is called a super dominating set of G, if for every vertex u∈S¯=V∖S, there exists a v∈S such that N(v)∩S¯=N(v)∖S=u. Analogously, the SDSP is to find a minimum-size super dominating set, and the corresponding minimum size, the super domination number of G. The decision variants of both the DSP and the SDSP have been shown to be NP-hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, r-clique sum, and the Hajós sum of two graphs. Additionally, we present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some graph classes. In particular, the number of super dominating sets for cycles has quite surprising properties as it varies between values of the set {4,n,2n,5n2−10n8} based on nmod4.
Downloadable publication This is an electronic reprint of the original article. |  |
