A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Super domination: Graph classes, products and enumeration
Tekijät: Ghanbari Nima, Jäger Gerold, Lehtilä Tuomo
Kustantaja: Elsevier
Julkaisuvuosi: 2024
Journal: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: Discrete Applied Mathematics
Vuosikerta: 349
Aloitussivu: 8
Lopetussivu: 24
ISSN: 0166-218X
eISSN: 1872-6771
DOI: https://doi.org/10.1016/j.dam.2024.01.039
Verkko-osoite: https://doi.org/10.1016/j.dam.2024.01.039
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/386892683
Preprintin osoite: 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
