Inverse Domination Number of a Graph: A Survey
Abstract
A subset $S$ of the vertex set of a graph $G$ is a dominating set if every
vertex in the complement of $S$ is adjacent to some vertex of~$S$. The minimum
cardinality among all minimal dominating sets is the domination number of
the graph~$G$. For a minimal dominating set $D$ of $G$ if the graph does not have
any isolated vertices, then $V-D$ contains a dominating set. Such a
dominating set in $V-D$ is called an inverse dominating set of $G$ and the
minimum cardinality among all inverse dominating sets is called the inverse
domination number. This paper surveys existing results on inverse dominating
sets, inverse domination number and lists some open problems on these
concepts.
The Kulli-Sigarkanti conjecture on inverse domination number is settled.
Downloads
References
\bibitem{11}
Bhat, P. G. and Bhat, S. R., {\it Inverse independence number of a
graph}, \textit{International Journal of Computer Applications}, 42(5), 9--13, (2012).
\bibitem{12}
Chaluvaraju, B. and Lokesha, V. and Kumar, C. N., {\it The dual neighborhood number of a graph}, Int. J. Contemp. Math. Sci., 5(47), 2327--2334, (2010).
\bibitem{6} Cockayne, E. J. and Hedetniemi, S. T., {\it Towards a theory of domination}, Networks, 7, 247--261, (1977).
\bibitem{21}
Cynthia, V. J. A and Kavitha, A., {\it Inverse Domination Number of Generalized Petersen Graph}, Int. J. Pure Appl. Math., 109(10), 69--77, (2016).
\bibitem{8} De Jaenisch, C. F., {\it Applications de l’Analyse Mathematique au Jeu des Echecs}, Petrograd, (1862).
\bibitem{13}
Domke, G. S., Dunbar, J. E. and Markus, L. R., {\it The inverse domination number of a graph}, Ars Comb., 72, 149--160, (2004).
\bibitem{15}
Driscoll, K. and Krop, E., {\it Some results related to the {Kulli}-{Sigarkanti} conjecture}, Congr. Numerantium, 231, 137--142, (2018).
\bibitem{14}
Frendrup, A., Henning, M. A., Randerath, B. and Vestergaard, P. D., {\it On a conjecture about inverse domination in graphs}, Ars Comb., 97A, 129--143, (2010).
\bibitem{18}
Frendrup, A., Henning, M. A., Randerath, B. and Vestergaard, P. D., {\it On a conjecture about inverse domination in graphs}, Ars Comb., 97A, 129--143, (2010).
\bibitem{4}
Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., {\it Fundamentals of domination in graphs}, Marcel Dekker, Inc., New York, (1988).
\bibitem{5}
Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., {\it Domination in graphs: {Advanced} topics}, Marcel Dekker, Inc., New York, (1998).
\bibitem{16}
Jayasree, T. G. and Iyer, R. R., {\it Results on the Inverse Domination
Number of Some Classes of Graphs}, International Journal of Mechanical
Engineering and Technology, 9(1), 995--1004, (2018).
\bibitem{17}
Kiunisala, E. M. and Jamil, F. P., {\it Inverse domination numbers and disjoint domination numbers of graphs under some binary operations}, Applied Mathematical Sciences, 8(107), 5303--5315, (2014).
\bibitem{20}
Krop, E., McDonald, J. and Puleo, G. J., {\it Upper bounds for inverse domination in graphs}, Theory Appl. Graphs, 8(2) Articled Number: 9, 9 Pages, (2021).
\bibitem{9}
Kulli, V. R. and Sigarkanti, S. C., {\it Inverse domination in graphs}, Natl. Acad. Sci. Lett., 14(12), 473--475, (1991).
\bibitem{10}
Kulli, V. R. and Iyer, R. R., {\it Inverse vertex covering number of a graph}, J. Discrete Math. Sci. Cryptography, 15(6), 389--393, (2012).
\bibitem{2} Ore, O., {\it Theory of graphs}, American Mathematical Society (AMS), Providence, RI, (1962).
\bibitem{7}
Walikar, H. B., Acharya, B. D. and Sampathkumar, E., {\it Recent Developments in the Theory of Domination in Graphs}, MRI Lecture Notes in Mathematics, Volume 1, (1979).
\bibitem{1}
West, D. B., {\it Introduction to Graph Theory}, Prentice-Hall of India, New Delhi, (2005).
Copyright (c) 2025 Boletim da Sociedade Paranaense de Matemática
This work is licensed under a Creative Commons Attribution 4.0 International License.
When the manuscript is accepted for publication, the authors agree automatically to transfer the copyright to the (SPM).
The journal utilize the Creative Common Attribution (CC-BY 4.0).
