{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:59:55Z","timestamp":1775717995314,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T00:00:00Z","timestamp":1772668800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T00:00:00Z","timestamp":1772668800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00373-026-03028-6","type":"journal-article","created":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T02:53:43Z","timestamp":1772679223000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Classification of Graphs Via Vertex Cover and Domination Numbers"],"prefix":"10.1007","volume":"42","author":[{"given":"Robert D.","family":"Barish","sequence":"first","affiliation":[]},{"given":"Shinya","family":"Fujita","sequence":"additional","affiliation":[]},{"given":"Farshad","family":"Kazemnejad","sequence":"additional","affiliation":[]},{"given":"Behnaz","family":"Pahlousay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,5]]},"reference":[{"key":"3028_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica 33, 461\u2013493 (2002). https:\/\/doi.org\/10.1007\/s00453-001-0116-5","journal-title":"Algorithmica"},{"issue":"3","key":"3028_CR2","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1002\/jgt.3190030305","volume":"3","author":"A Blass","year":"1979","unstructured":"Blass, A., Harary, F.: Properties of almost all graphs and complexes. J. Graph Theory 3(3), 225\u2013240 (1979). https:\/\/doi.org\/10.1002\/jgt.3190030305","journal-title":"J. Graph Theory"},{"key":"3028_CR3","doi-asserted-by":"crossref","unstructured":"Bondy, J. A., Murty, U. S. R.: Graph theory. Graduate texts in mathematics, vol. 244, Springer Science and Media, (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"3028_CR4","unstructured":"Brod\u00e9n, B., Hammar, M., Nilsson, B. J.: Guarding lines and 2-link polygons is APX-hard. Proc. 13th Canadian Conference on Computational Geometry (CCCG \u201901), pp. 45\u201348 (2001)"},{"key":"3028_CR5","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory Ser. B 18(1), 39\u201341 (1975). https:\/\/doi.org\/10.1016\/0095-8956(75)90061\u20131","DOI":"10.1016\/0095-8956(75)90061-1"},{"key":"3028_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Springer-Verlag, London (2013)"},{"issue":"1\u20132","key":"3028_CR7","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0166-218X(95)00056-W","volume":"68","author":"JE Dunbar","year":"1996","unstructured":"Dunbar, J.E., Goddard, W., Hedetniemi, S.T., McRae, A.A., Henning, M.A.: The algorithmic complexity of minus domination in graphs. Discret. Appl. Math. 68(1\u20132), 73\u201384 (1996)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"3028_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","volume":"326","author":"F Eisenbrand","year":"2004","unstructured":"Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theoret. Comput. Sci. 326(1\u20133), 57\u201367 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.05.009","journal-title":"Theoret. Comput. Sci."},{"key":"3028_CR9","doi-asserted-by":"publisher","unstructured":"Fischer, N., K\u00fcnnemann, M., Redzic, M.: The effect of sparsity on k-dominating set and related first-order graph properties. Proc. 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201924), pp. 4704\u20134727 (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.168","DOI":"10.1137\/1.9781611977912.168"},{"issue":"3","key":"3028_CR10","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0095-8956(78)90059-X","volume":"24","author":"S Fisk","year":"1978","unstructured":"Fisk, S.: A short proof of Chv\u00e1tal\u2019s watchman theorem. J. Comb. Theory Ser. B 24(3), 374 (1978). https:\/\/doi.org\/10.1016\/0095-8956(78)90059-X","journal-title":"J. Comb. Theory Ser. B"},{"key":"3028_CR11","doi-asserted-by":"crossref","unstructured":"Fujita, S., Kazemnejad, F., Pahlavsay, B.: New classification of graphs in view of the domination number of central graphs. arXiv:2204.10292 (April 2022)","DOI":"10.5614\/ejgta.2022.10.1.19"},{"key":"3028_CR12","doi-asserted-by":"crossref","unstructured":"Hajian, M., Henning, M.A., N.: J. Rad. A classification of cactus graphs according to their domination number. Discuss. Math. Graph Theory 42(2), 613\u2013626 (2022)","DOI":"10.7151\/dmgt.2295"},{"key":"3028_CR13","volume-title":"Graphical enumeration","author":"F Harary","year":"1973","unstructured":"Harary, F., Palmer, E.M.: Graphical enumeration. Academic Press, New York, NY (1973)"},{"issue":"1","key":"3028_CR14","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7151\/dmgt.1296","volume":"26","author":"LM Harris","year":"2006","unstructured":"Harris, L.M., Hattingh, J.H., Henning, M.A.: Algorithmic aspects of total k-subdomination in graphs. Discuss. Math. Graph Theory 26(1), 5\u201318 (2006)","journal-title":"Discuss. Math. Graph Theory"},{"key":"3028_CR15","volume-title":"Domination in graphs: advanced topics","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in graphs: advanced topics. Marcel Dekker, New York, NY (1998)"},{"key":"3028_CR16","volume-title":"Fundamentals of domination in graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Marcel Dekker, New York, NY (1998)"},{"key":"3028_CR17","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2018.09.019","volume":"766","author":"MA Henning","year":"2019","unstructured":"Henning, M.A., Pandey, A.: Algorithmic aspects of semitotal domination in graphs. Theoret. Comput. Sci. 766, 46\u201357 (2019)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"3028_CR18","doi-asserted-by":"publisher","first-page":"359","DOI":"10.26493\/1855-3974.1525.7f3","volume":"16","author":"MA Henning","year":"2019","unstructured":"Henning, M.A., Peterin, I.: A characterization of graphs with disjoint total dominating sets. Ars Math. Contemp. 16(2), 359\u2013375 (2019)","journal-title":"Ars Math. Contemp."},{"issue":"2","key":"3028_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s10878-009-9274-1","volume":"22","author":"MA Henning","year":"2011","unstructured":"Henning, M.A., Southey, J.: A characterization of graphs with disjoint dominating and paired-dominating sets. J. Comb. Optim. 22(2), 217\u2013234 (2011)","journal-title":"J. Comb. Optim."},{"key":"3028_CR20","doi-asserted-by":"crossref","unstructured":"Henning, M. A., Yeo, A.: Total domination in graphs. Springer Monographs in Mathematics, (2013)","DOI":"10.1007\/978-1-4614-6525-6"},{"issue":"6","key":"3028_CR21","doi-asserted-by":"publisher","first-page":"7214","DOI":"10.3934\/math.2020461","volume":"5","author":"TK Jahfar","year":"2020","unstructured":"Jahfar, T.K., Chithra, A.V.: Central vertex join and central edge join of two graphs. AIMS Math. 5(6), 7214\u20137233 (2020). https:\/\/doi.org\/10.3934\/math.2020461","journal-title":"AIMS Math."},{"key":"3028_CR22","unstructured":"Jahfar, T. K., Chithra, A. V.: Spectra of new graph operations based on central graph. ArXiv:2107.00854 (2021)"},{"key":"3028_CR23","doi-asserted-by":"publisher","unstructured":"Karp, R. M.: Reducibility among combinatorial problems. Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, Eds.; Plenum Press: New York, NY) (1972), pp. 85\u2013103, https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"3028_CR24","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.4134\/BKMS.b180891","volume":"56","author":"F Kazemnejad","year":"2019","unstructured":"Kazemnejad, F., Moradi, S.: Total domination number of central graphs. Bull. Korean Math. Soc. 56(4), 1059\u20131075 (2019). https:\/\/doi.org\/10.4134\/BKMS.b180891","journal-title":"Bull. Korean Math. Soc."},{"key":"3028_CR25","unstructured":"Kazemnejad, F., Pahlavsay, B., Palezzato, E., Torielli, M.: Domination number of middle graphs. ArXiv:2008.02975 (2020)"},{"key":"3028_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21708-5","volume-title":"Combinatorial optimization: theory and algorithms","author":"B Korte","year":"2000","unstructured":"Korte, B., Vygen, J.: Combinatorial optimization: theory and algorithms. Springer, Berlin (2000)"},{"issue":"2","key":"3028_CR27","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"DT Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276\u2013282 (1986). https:\/\/doi.org\/10.1109\/TIT.1986.1057165","journal-title":"IEEE Trans. Inf. Theory"},{"key":"3028_CR28","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94\u2013112 (2014). https:\/\/doi.org\/10.1016\/j.jsc.2013.09.003","journal-title":"J. Symb. Comput."},{"key":"3028_CR29","doi-asserted-by":"crossref","unstructured":"Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1(5), 194\u2013197 (1982). https:\/\/doi.org\/10.1016\/0167-6377(82)90039\u20136","DOI":"10.1016\/0167-6377(82)90039-6"},{"key":"3028_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01363123","volume":"174","author":"W Oberschelp","year":"1967","unstructured":"Oberschelp, W.: Kombinatorische anzahlbestimmungen in relationen. Math. Ann. 174, 53\u201378 (1967). https:\/\/doi.org\/10.1007\/BF01363123","journal-title":"Math. Ann."},{"key":"3028_CR31","volume-title":"Art gallery theorems and algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art gallery theorems and algorithms. Oxford University Press, New York, NY (1987)"},{"issue":"3","key":"3028_CR32","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1007\/s00373-021-02297-7","volume":"37","author":"B Pahlavsay","year":"2021","unstructured":"Pahlavsay, B., Palezzato, E., Torielli, M.: Domination in latin square graphs. Graphs and Combinatorics 37(3), 971\u2013985 (2021). https:\/\/doi.org\/10.1007\/s00373-021-02297-7","journal-title":"Graphs and Combinatorics"},{"key":"3028_CR33","doi-asserted-by":"publisher","first-page":"15","DOI":"10.7151\/dmgt.2242","volume":"42","author":"B Pahlavsay","year":"2022","unstructured":"Pahlavsay, B., Palezzato, E., Torielli, M.: 3-Tuple total domination number of rook\u2019s graphs. Discuss. Math. Graph Theory 42, 15\u201337 (2022). https:\/\/doi.org\/10.7151\/dmgt.2242","journal-title":"Discuss. Math. Graph Theory"},{"key":"3028_CR34","doi-asserted-by":"publisher","unstructured":"Patil, H.P., Pandiya Raj, R.: On the total graph of Mycielski graphs, central graphs and their covering numbers. Discuss. Math. Graph Theory 33(2), 361\u2013371 . https:\/\/doi.org\/10.7151\/dmgt.1670","DOI":"10.7151\/dmgt.1670"},{"issue":"3","key":"3028_CR35","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1112\/jlms\/s1-26.3.198","volume":"26","author":"KF Roth","year":"1951","unstructured":"Roth, K.F.: On a problem of Heilbronn. J. London Math. Soc. s1\u2013 26(3), 198\u2013204 (1951). https:\/\/doi.org\/10.1112\/jlms\/s1-26.3.198","journal-title":"J. London Math. Soc. s1\u2013"},{"key":"3028_CR36","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2018.10.030","volume":"770","author":"JA Telle","year":"2019","unstructured":"Telle, J.A., Villanger, Y.: FPT algorithms for domination in sparse graphs and beyond. Theoret. Comput. Sci. 770, 62\u201368 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.10.030","journal-title":"Theoret. Comput. Sci."},{"key":"3028_CR37","unstructured":"Ueda, N., Nagao. T.: NP-completeness results for NONOGRAM via parsimonious reductions. Technical Report TR96-0008 (ISSN 0918\u20132802), Department of Computer Science, Tokyo Institute of Technology, Japan (May 1996)"},{"key":"3028_CR38","unstructured":"Vernold, J. V.: Harmonious coloring of total graphs, $$n$$-leaf, central graphs and circumdetic graphs. Ph.D Thesis, Bharathiar University, Coimbatore, India (2007)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-026-03028-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-026-03028-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-026-03028-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:16:01Z","timestamp":1775715361000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-026-03028-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,5]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["3028"],"URL":"https:\/\/doi.org\/10.1007\/s00373-026-03028-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,5]]},"assertion":[{"value":"14 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"33"}}