EN|RU
English version: Journal of Applied and Industrial Mathematics, 2020, 14:2, 353-368 |
![]() |
Volume 27, No 2, 2020, P. 65-89 UDC 519.17
Keywords: independent dominating set, cubic graph, planar graph, bipartite graph, NP-completeness. DOI: 10.33048/daio.2020.27.657 Yaroslav A. Loverov 1 Received April 11, 2019 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). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|