{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T14:15:56Z","timestamp":1758636956090,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T00:00:00Z","timestamp":1722643200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T00:00:00Z","timestamp":1722643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100005276","name":"National Board for Higher Mathematics","doi-asserted-by":"publisher","award":["NBHM\/02011\/24\/2023\/6051"],"award-info":[{"award-number":["NBHM\/02011\/24\/2023\/6051"]}],"id":[{"id":"10.13039\/501100005276","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001409","name":"Department of Science and Technology, Ministry of Science and Technology, India","doi-asserted-by":"publisher","award":["DST\/CRG\/2023\/007127"],"award-info":[{"award-number":["DST\/CRG\/2023\/007127"]}],"id":[{"id":"10.13039\/501100001409","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00236-024-00461-z","type":"journal-article","created":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T15:02:09Z","timestamp":1722697329000},"page":"357-382","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A closer look at Hamiltonicity and domination through the lens of diameter and convexity"],"prefix":"10.1007","volume":"61","author":[{"given":"R.","family":"Mahendra Kumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Sadagopan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,3]]},"reference":[{"issue":"3","key":"461_CR1","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1287\/opre.32.3.478","volume":"32","author":"A Agrawal","year":"1984","unstructured":"Agrawal, A., Barlow, R.E.: A survey of network reliability and domination theory. Oper. Re. 32(3), 478\u2013492 (1984)","journal-title":"Oper. Re."},{"issue":"1","key":"461_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"AA Bertossi","year":"1984","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19(1), 37\u201340 (1984)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"461_CR3","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"MS Chang","year":"1998","unstructured":"Chang, M.S.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27(6), 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"461_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10878-015-9917-3","volume":"32","author":"H Chen","year":"2016","unstructured":"Chen, H., Lei, Z., Liu, T., Tang, Z., Wang, C., Xu, K.: Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs. J. Comb. Optim. 32(1), 95\u2013110 (2016)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"461_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discret. Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discret. Appl. Math."},{"key":"461_CR6","first-page":"35","volume":"38","author":"J Cyman","year":"2007","unstructured":"Cyman, J.: The outer-connected domination number of a graph. Australas. J. Comb. 38, 35\u201346 (2007)","journal-title":"Australas. J. Comb."},{"issue":"3","key":"461_CR7","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1137\/S0097539791200375","volume":"23","author":"JS Deogun","year":"1994","unstructured":"Deogun, J.S., Steiner, G.: Polynomial algorithms for hamiltonian cycle in cocomparability graphs. SIAM J. Comput. 23(3), 520\u2013552 (1994)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Shmoys DB, editor. Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014 ACM; 2014. pp. 624\u2013633. https:\/\/doi.org\/10.1145\/2591796.2591884","key":"461_CR8","DOI":"10.1145\/2591796.2591884"},{"issue":"2","key":"461_CR9","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0166-218X(92)00171-H","volume":"50","author":"D Dorninger","year":"1994","unstructured":"Dorninger, D.: Hamiltonian circuits determining the order of chromosomes. Discret. Appl. Math. 50(2), 159\u2013168 (1994)","journal-title":"Discret. Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier (2004)","key":"461_CR10","DOI":"10.1016\/S0167-5060(04)80051-7"},{"unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs Marcel Dekker. Inc, New York (1998)","key":"461_CR11"},{"issue":"1\u20133","key":"461_CR12","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/j.tcs.2005.04.009","volume":"341","author":"RW Hung","year":"2005","unstructured":"Hung, R.W., Chang, M.S.: Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs. Theoret. Comput. Sci. 341(1\u20133), 411\u2013440 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"461_CR13","first-page":"85","volume":"23","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Complexity of computer computations, chapter reducibility among combinatorial problems. Plenum Press Surv. State-of-the-Art 23, 85\u2013104 (1972)","journal-title":"Plenum Press Surv. State-of-the-Art"},{"issue":"4","key":"461_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"JM Keil","year":"1985","unstructured":"Keil, J.M.: Finding Hamiltonian circuits in interval graphs. Inf. Process. Lett. 20(4), 201\u2013206 (1985)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"461_CR15","doi-asserted-by":"publisher","first-page":"498","DOI":"10.2307\/2273574","volume":"48","author":"HR Lewis","year":"1983","unstructured":"Lewis, H.R., Michael, R.A.: $$\\Pi $$Garey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. WH Freeman and Company, San Francisco1979, x+ 338 pp. J. Symb. Log. 48(2), 498\u2013500 (1983)","journal-title":"J. Symb. Log."},{"issue":"2","key":"461_CR16","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/0378-4371(76)90002-9","volume":"84","author":"A Malakis","year":"1976","unstructured":"Malakis, A.: Hamiltonian walks and polymer configurations. Phys. A: Stat. Mech. Appl. 84(2), 256\u2013284 (1976)","journal-title":"Phys. A: Stat. Mech. Appl."},{"doi-asserted-by":"crossref","unstructured":"Mohanapriya, A., Renjith, P., Sadagopan, N.: P versus NPC: minimum steiner trees in convex split graphs. In: Conference on Algorithms and Discrete Applied Mathematics, pp. 115\u2013126. Springer (2022)","key":"461_CR17","DOI":"10.1007\/978-3-030-95018-7_10"},{"issue":"1\u20133","key":"461_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian circuits in chordal bipartite graphs. Discret. Math. 156(1\u20133), 291\u2013298 (1996)","journal-title":"Discret. Math."},{"issue":"2\u20133","key":"461_CR19","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H M\u00fcller","year":"1987","unstructured":"M\u00fcller, H., Brandst\u00e4dt, A.: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theoret. Comput. Sci. 53(2\u20133), 257\u2013265 (1987)","journal-title":"Theoret. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Panda, B.S., Pandey, A.: Algorithm and hardness results for outer-connected dominating set in graphs. In: International Workshop on Algorithms and Computation. pp. 151\u2013162. Springer (2014)","key":"461_CR20","DOI":"10.1007\/978-3-319-04657-0_16"},{"key":"461_CR21","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.dam.2018.03.029","volume":"252","author":"A Pandey","year":"2019","unstructured":"Pandey, A., Panda, B.: Domination in some subclasses of bipartite graphs. Discret. Appl. Math. 252, 51\u201366 (2019)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"461_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-013-9703-z","volume":"31","author":"D Pradhan","year":"2016","unstructured":"Pradhan, D.: On the complexity of the minimum outer-connected dominating set problem in graphs. J. Comb. Optim. 31(1), 1\u201312 (2016)","journal-title":"J. Comb. Optim."},{"doi-asserted-by":"crossref","unstructured":"Renjith, P., Sadagopan, N.: Hamiltonian path in $$K_{1, r}$$-free split graphs-a dichotomy. In: Conference on Algorithms and Discrete Applied Mathematics. pp. 30\u201344. Springer (2018)","key":"461_CR23","DOI":"10.1007\/978-3-319-74180-2_3"},{"issue":"01","key":"461_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0129054121500337","volume":"33","author":"P Renjith","year":"2022","unstructured":"Renjith, P., Sadagopan, N.: Hamiltonian cycle in $$K_{1, r}$$-free split graphs-A dichotomy. Int. J. Found. Comput. Sci. 33(01), 1\u201332 (2022)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"461_CR25","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discret. Appl. Math. 18(3), 279\u2013292 (1987)","journal-title":"Discret. Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Telle, J.A., Villanger, Y.: FPT algorithms for domination in biclique-free graphs. In: Algorithms\u2013ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings 20. pp. 802\u2013812. Springer (2012)","key":"461_CR26","DOI":"10.1007\/978-3-642-33090-2_69"},{"doi-asserted-by":"crossref","unstructured":"Wang, Y.M., Chen, S.H., Chao, M.C.T.: An efficient hamiltonian-cycle power-switch routing for MTCMOS designs. In: 17th Asia and South Pacific Design Automation Conference. pp. 59\u201365. IEEE (2012)","key":"461_CR27","DOI":"10.1109\/ASPDAC.2012.6165026"},{"unstructured":"West, D.B., et\u00a0al.: Introduction to Graph Theory. vol.\u00a02. Prentice hall Upper Saddle River (2001)","key":"461_CR28"},{"unstructured":"Wu, J., Li, H.: Domination and its applications in ad hoc wireless networks with unidirectional links. In: Proceedings 2000 International Conference on Parallel Processing. pp. 189\u2013197. IEEE (2000)","key":"461_CR29"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00461-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-024-00461-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00461-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T11:03:07Z","timestamp":1730718187000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-024-00461-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,3]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["461"],"URL":"https:\/\/doi.org\/10.1007\/s00236-024-00461-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2024,8,3]]},"assertion":[{"value":"28 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2024","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 declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}