On the super domination number of graphs

Document Type : Original paper


1 Universitat Rovira i Virgili

2 Texas A&M University


The open neighborhood of a vertex $v$ of a graph $G$ is the set $N(v)$ consisting of all vertices adjacent to $v$ in $G$. For $D\subseteq V(G)$, we define $\overline{D}=V(G)\setminus D$. A set $D\subseteq V(G)$ is called a super dominating set of $G$ if for every vertex $u\in \overline{D}$, there exists $v\in D$ such that  $N(v)\cap \overline{D}=\{u\}$. The super domination number of $G$ is the minimum cardinality among all super dominating sets of $G$. In this paper, we obtain closed formulas and tight bounds for the super domination number of $G$ in terms of several invariants of $G$. We also obtain results on the super domination number of corona product graphs and Cartesian product graphs.


Main Subjects

[1] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979), no. 3, 241–249.
[2] B. Brešar, P. Dorbec, W. Goddard, B.L. Hartnell, M.A. Henning, S. Klavžar, and D.F. Rall, Vizing’s conjecture: a survey and recent results, J. Graph Theory 69 (2012), no. 1, 46–76.
[3] E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga, and J.H. van Vuuren, Protection of a graph, Util. Math. 67 (2005), 19–32.
[4] M. Dettlaff, M. Lemańska, J.A. Rodríguez-Velázquez, and R. Zuazua, On the super domination number of lexicographic product graphs, Discrete App. Math. 263 (2019), 118–129.
[5] J. Egerváry, Matrixok kombinatorikus tulajdonságair´ol, Matematikaiés Fizikai Lapok 38 (1931), 16–28.
[6] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970), no. 3, 322–325.
[7] R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, Discrete Mathematics and Its Applications, 2nd ed., CRC press, 2011.
[8] F. Harary, J.P. Hayes, and H.-J. Wu, A survey of the theory of hypercube graphs, Comput. Math. Appl. 15 (1988), no. 4, 277–289.
[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York,
[11] W. Imrich and S. Klavžar, Product Graphs, Structure and Recognition, WileyInterscience series in discrete mathematics and optimization, Wiley, 2000.
[12] D. König, Gráfokés mátrixok, Matematikaiés Fizikai Lapok 38 (1931), 116–119.
[13] D. Kuziak, M. Lemańska, and I.G. Yero, Domination-related parameters in rooted product graphs, Bull. Malays. Math. Sci. Soc. 39 (2016), no. 1, 199–217.
[14] 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), no. 3, 353–357.
[15] A. Meir and J. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975), no. 1, 225–233.
[16] V.G. Vizing, The cartesian product of graphs, Vyˇcisl. Sistemy 9 (1963), 30–43.
[17] H.B. Walikar, B.D. Acharya, and E. Sampathkumar, Recent Developments in the Theory of Domination in Graphs and its applications, vol. 1, MRI Lecture Notes in Mathematics, 1979.