On the super domination number of graphs

Document Type : Original paper

Authors

1 Universitat Rovira i Virgili

2 Texas A&M University

Abstract

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.

Keywords

Main Subjects

References

[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,
1998.
[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.
Communications in Combinatorics and Optimization
Volume 5, Issue 2
December 2020
Pages 83-96

Files

Share

How to cite

Statistics