论文标题

在图中结束超级统治集

End Super Dominating Sets in Graphs

论文作者

Akbari, Saieed, Ghanbari, Nima, Henning, Michael A.

论文摘要

令$ g =(v,e)$为一个简单的图。 $ g $的主导集是一个子集$ s \ subseteq v $,因此每个顶点$ s $中的每个顶点至少与$ s $中的至少一个顶点相邻。由$γ(g)$表示的最小统治$ g $的基数是$ g $的统治数。如果两个顶点是邻居,则是邻居。超级主导套件是一个主导的集合$ s $,其附加属性是$ v \ setminus s $中的每个顶点的$ s $中的邻居,该邻居与$ v \ setminus s $相邻的$ s $中。此外,如果$ v \ setminus s $中的每个顶点至少具有〜$ 2 $,则$ s $是最终超级统治集。末端超级统治数是末端超统治集的最小基数。我们将最终超级主导集的应用程序作为网络的主要服务器和临时服务器。我们确定了特定图类别的最终超级支配数的确切值,并计算这些图中的端端超统治集的数量。末端超级统治数的紧密上限是建立的,其中图通过顶点(边缘)的去除和收缩进行了修改。

Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $S\subseteq V$ such that every vertex not in $S$ is adjacent to at least one vertex in $S$. The cardinality of a smallest dominating set of $G$, denoted by $γ(G)$, is the domination number of $G$. Two vertices are neighbors if they are adjacent. A super dominating set is a dominating set $S$ with the additional property that every vertex in $V \setminus S$ has a neighbor in $S$ that is adjacent to no other vertex in $V \setminus S$. Moreover if every vertex in $V \setminus S$ has degree at least~$2$, then $S$ is an end super dominating set. The end super domination number is the minimum cardinality of an end super dominating set. We give applications of end super dominating sets as main servers and temporary servers of networks. We determine the exact value of the end super domination number for specific classes of graphs, and we count the number of end super dominating sets in these graphs. Tight upper bounds on the end super domination number are established, where the graph is modified by vertex (edge) removal and contraction.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源