Geodesic
NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 65-89.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : independent dominating set, cubic graph, planar graph, bipartite graph, NP-completeness. 
@article{DA_2020_27_2_a3,
     author = {Ya. A. Loverov and Yu. L. Orlovich},
     title = {NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {65--89},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2020},
     language = {ru},
     url = {https://geodesic-test.mathdoc.fr/item/DA_2020_27_2_a3/}
}
TY  - JOUR
AU  - Ya. A. Loverov
AU  - Yu. L. Orlovich
TI  - NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 65
EP  - 89
VL  - 27
IS  - 2
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DA_2020_27_2_a3/
LA  - ru
ID  - DA_2020_27_2_a3
ER  - 
%0 Journal Article
%A Ya. A. Loverov
%A Yu. L. Orlovich
%T NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 65-89
%V 27
%N 2
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DA_2020_27_2_a3/
%G ru
%F DA_2020_27_2_a3
Ya. A. Loverov; Yu. L. Orlovich. NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 65-89. https://geodesic-test.mathdoc.fr/item/DA_2020_27_2_a3/

[1] Ore O., Theory of graphs, Amer. Math. Soc., Providence, RI, 1962, 284 pp. | MR | Zbl

[2] Cockayne E. J., Hedetniemi S. T., “Independence graphs”, Congr. Numerantium, 10 (1974), 471–491 | MR

[3] Sampathkumar E., Walikar H. B., “The connected domination number of a graph”, J. Math. Phys. Sci., 13 (1979), 607–613 | MR | Zbl

[4] Cockayne E. J., Dawes R. M., Hedetniemi S. T., “Total domination in graphs”, Networks, 10 (1980), 211–219 | DOI | MR | Zbl

[5] Bollobás B., Cockayne E. J., “Graph-theoretic parameters concerning domination, independence, and irredundance”, J. Graph Theory, 3:3 (1979), 241–249 | DOI | MR | Zbl

[6] Cockayne E. J., Hartnell B. L., Hedetniemi S. T., Laskar R., “Perfect domination in graphs”, J. Comb. Inf. Syst. Sci., 18 (1993), 136–148 | MR | Zbl

[7] Sampathkumar E., Neeralagi P. S., “The neighbourhood number of a graph”, Indian J. Pure Appl. Math., 16 (1985), 126–132 | MR | Zbl

[8] Sampathkumar E., Neeralagi P. S., “Independent, perfect and connected neighbourhood numbers of a graph”, J. Comb. Inf. Syst. Sci., 19 (1994), 139–145 | MR | Zbl

[9] Haynes T. W., Hedetniemi S. T., Slater P. J., Domination in graphs: Advanced topics, Marcel Dekker, New York, 1998, 520 pp. | MR | Zbl

[10] Haynes T. W., Hedetniemi S. T., Slater P. J., Fundamentals of domination in graphs, Marcel Dekker, New York, 1998, 457 pp. | MR | Zbl

[11] Du D.-Z., Wan P.-J., Connected dominating set: Theory and applications, Springer, New York, 2013, 216 pp. | MR | Zbl

[12] Goddard W., Henning M. A., “Independent domination in graphs: A survey and recent results”, Discrete Math., 313 (2013), 839–854 | DOI | MR | Zbl

[13] Henning M., Yeo A., Total domination in graphs, Springer, New York, 2013, 192 pp. | MR | Zbl

[14] Liu C.-H., Poon S.-H., Lin J.-Y., “Independent dominating set problem revisited”, Theor. Comput. Sci., 562 (2015), 1–22 | DOI | MR | Zbl

[15] Berge C., Graphs and hypergraphs, North-Holland, Amsterdam, 1973, 528 pp. | MR | Zbl

[16] Topp J., Domination, independence and irredundance in graphs, Diss. Math., 342, Inst. Mat. PAN, Warsaw, 1995, 98 pp. | MR

[17] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[18] Manlove D. F., “On the algorithmic complexity of twelve covering and independence parameters of graphs”, Discrete Appl. Math., 91 (1999), 155–175 | DOI | MR | Zbl

[19] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994 | MR | MR