This article is cited in 4 papers

NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs

Ya. A. Loverov, Yu. L. Orlovich

Belarusian State University, Nezavisimosti Avenue, 4, 220030 Minsk, Belarus

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.

UDC: 519.17

Received: 11.04.2019
Revised: 20.12.2019
Accepted: 13.01.2020

DOI: 10.33048/daio.2020.27.657

 English version: Journal of Applied and Industrial Mathematics, 2020, 14:2, 352–366

Bibliographic databases:

•