Article in press
Authors:
Title:
End super dominating sets in graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-02-17 , Revised: 2023-08-19 , Accepted: 2023-08-21 , Available online: 2023-09-25 , https://doi.org/10.7151/dmgt.2519
Abstract:
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
$\gamma(G)$, is the domination number of $G$. 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.
Keywords:
domination number, end super dominating set, end super domination number, networks, generalization
References:
- S. Akbari, P.J. Cameron and G.B. Khosrovshahi, Ranks and signatures of adjacency matrices (2004).
https://webspace.maths.qmul.ac.uk/p.j.cameron/preprints/ranksign.pdf - B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249.
https://doi.org/10.1002/jgt.3190030306 - J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, MacMillan, New York, London, 1976).
- M. Dettlaff, M. Lemańska, J.A. Rodríguez-Velázquez and R. Zuazua, On the super domination number of lexicographic product graphs, Discrete Appl. Math. 263 (2019) 118–129.
https://doi.org/10.1016/j.dam.2018.03.082 - N. Ghanbari, Some results on the super domination number of a graph, Discrete Math. Algorithms Appl.(2023), in press.
https://doi.org/10.1142/S1793830923500441 - N. Ghanbari and S. Alikhani, Total dominator chromatic number of some operations on a graph, Bull. Comput. Appl. Math. 6 (2018) 9–20.
- N. Ghanbari, G. Jäger and T. Lehtilä, Super domination: graph classes, products and enumeration (2022), a manuscript.
arXiv: 2209.01795 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Structures of Domination in Graphs, Dev. Math. 66 (Springer, Cham, 2021).
https://doi.org/10.1007/978-3-030-58892-2 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-09496-5 - M.A. Henning and A. Yeo, Total Domination in Graphs, Springer Monogr. Math. (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - F. Jaeger and C. Payan, Relations du type Nordhaus-Gaddum pour le nombre d'absorption d'un graphe simple, C.R. Acad. Sci. Paris A 274 (1972) 728–730.
- M. Lemańska, V. Swaminathan, Y.B. Venkatakrishnan and R. Zuazua, Super dominating sets in graphs, Proc. Nat. Acad. Sci. India Sect. A 85 (2015) 353–357.
https://doi.org/10.1007/s40010-015-0208-2 - E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer.\ Math.\ Monthly 63 (1956) 175–177.
https://doi.org/10.2307/2306658 - V.G. Vizing, An estimate of the external stability number of a graph, Dokl. Akad. Nauk SSSR 164 (1965) 729–731.
- H.B. Walikar, B.D. Acharya and E. Sampathkumar, Recent Developments in the Theory of Domination in Graphs, Lecture Notes in Math. (Mehta Research Institute, Allahabad, MRI, 1979).
Close