Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:2, 353-368
Volume 27, No 2, 2020, P. 65-89
UDC 519.17
Ya. A. Loverov and Yu. L. Orlovich
NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
Abstract:
It is known that the independent dominating set problem is NP-complete both in the class of cubic planar graphs and in the class of cubic bipartite graphs. The question about the computational complexity of the problem in the intersection of these graph classes has remained open. In this article, we prove that the independent dominating set problem is NP-complete in the class of cubic planar bipartite graphs.
Tab. 1, illustr. 7, bibliogr. 19.
Keywords: independent dominating set, cubic graph, planar graph, bipartite graph, NP-completeness.
DOI: 10.33048/daio.2020.27.657
Yaroslav A. Loverov 1
Yury L. Orlovich 1
1. Belarusian State University,
Nezavisimosti Avenue, 4, 220030 Minsk, Belarus
e-mail: loverov@bsu.by, orlovich@bsu.by
Received April 11, 2019
Revised December 20, 2019
Accepted January 13, 2020
References
[1] O. Ore, Theory of Graphs (Amer. Math. Soc., Providence, RI, 1962).[2] E. J. Cockayne and S. T. Hedetniemi, Independence graphs, Congr. Numerantium 10, 471–491 (1974).
[3] E. Sampathkumar and H. B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13, 607–613 (1979).
[4] E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs, Networks 10, 211–219 (1980).
[5] B. Bollobás and E. J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (3), 241–249 (1979).
[6] E. J. Cockayne, B. L. Hartnell, S. T. Hedetniemi, and R. Laskar, Perfect domination in graphs, J. Comb. Inf. Syst. Sci. 18, 136–148 (1993).
[7] E. Sampathkumar and P. S. Neeralagi, The neighbourhood number of a graph, Indian J. Pure Appl. Math. 16, 126–132 (1985).
[8] E. Sampathkumar and P. S. Neeralagi, Independent, perfect and connected neighbourhood numbers of a graph, J. Comb. Inf. Syst. Sci. 19, 139–145 (1994).
[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] D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications (Springer, New York, 2013).
[12] W. Goddard and M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313, 839–854 (2013).
[13] M. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013).
[14] C.-H. Liu, S.-H. Poon, and J.-Y. Lin, Independent dominating set problem revisited, Theor. Comput. Sci. 562, 1–22 (2015).
[15] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).
[16] J. Topp, Domination, Independence and Irredundance in Graphs (Inst. Mat. PAN, Warsaw, 1995) (Diss. Math., Vol. 342) 1995.
[17] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
[18] D. F. Manlove, On the algorithmic complexity of twelve covering and independence parameters of graphs, Discrete Appl. Math. 91, 155–175 (1999).
[19] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990 [Russian]; B. I. Wissenschaftsverlag, Mannheim, 1994).
