End Super Dominating Sets in Graphs

arXiv2209.02980MaRDI QIDQ6409941FDOQ6409941

S. Akbari, N. Ghanbari, Michael A. Henning

Publication date: 7 September 2022

Abstract: Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $SsubseteqV$ 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 $gamma(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 $VsetminusS$ has a neighbor in $S$ that is adjacent to no other vertex in $VsetminusS$. Moreover if every vertex in $VsetminusS$ 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.

Mathematics Subject Classification ID

Applications of graph theory (05C90) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

This page was built for publication: End Super Dominating Sets in Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409941)