论文标题
超级统治：图类，产品和枚举
Super Domination: Graph Classes, Products and Enumeration
论文作者
论文摘要
主导集问题（DSP）是组合优化中最著名的问题之一。它的定义如下。对于给定的简单图$ g =（v，e）$，$ g $的统治集是一个子集$ s \ subseteq v $，使得$ v \ setminus s $中的每个顶点均与至少一个$ s $中的一个顶点相邻。此外，DSP是找到最小尺寸的主导集和相应的最小尺寸（$ g $的支配数字）的问题。 在这项工作中，我们研究了DSP的一种变体，即超级主导的集合问题（SDSP），在过去几年中引起了很多关注。如果每个顶点$ u \ in \ In \ overline {s} = v \ setMinus s $，则称为$ g $的超级统治集$ s $，则在s $中存在$ v \，以便$ n（v）\ cap \ cap \ cap \ cap \ cap \ cap \ overline {s} = \ \ \ \ \ \ \ \ \ {u \} $。类似地，SDSP是要找到一个最小尺寸的超统治组，以及相应的最小尺寸，即$ g $的超级统治数。 DSP和SDSP的决策变体已证明是$ \ Mathcal {np} $ - 硬。 在本文中，我们介绍了邻里电晕产品的超级统治数，$ r $ $ $ $ $ $ $ $ $ $，以及两个图的Hajós和。此外，我们提出了达到我们界限的无限图。最后，我们为某些图形类提供了确切的最小尺寸超统治集的数量。特别是，循环的超级主导集的数量具有令人惊讶的属性，因为它在集合$ \ {4，n，n，2n，\ frac {5n^2-10n} {8} {8} \} $的基于$ n \ mod4 $之间。
The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given simple graph $G=(V,E)$, 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$. 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\in \overline{S}=V \setminus S$, there exists a $v\in S$ such that $N(v)\cap \overline{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 shown to be $\mathcal{NP}$-hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, $r$-gluing, 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,\frac{5n^2-10n}{8}\}$ based on $n\mod4$.
