{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:09:01Z","timestamp":1753880941990,"version":"3.41.2"},"reference-count":45,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["ECR\/2017\/001442"],"award-info":[{"award-number":["ECR\/2017\/001442"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p> For a connected graph, a path containing all vertices is known as a Hamiltonian path. For general graphs, there is no known necessary and sufficient condition for the existence of Hamiltonian paths and the complexity of finding a Hamiltonian path in general graphs is NP-Complete. We present a necessary and sufficient condition for the existence of Hamiltonian paths in 2-trees. Using our characterization, we also present a linear-time algorithm for the existence of Hamiltonian paths in 2-trees. Our characterization is based on a deep understanding of the structure of 2-trees and the combinatorics presented here may be used in other combinatorial problems restricted to 2-trees. <\/jats:p>","DOI":"10.1142\/s1793830922501130","type":"journal-article","created":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T08:21:31Z","timestamp":1653553291000},"source":"Crossref","is-referenced-by-count":0,"title":["2-Trees: Structural insights and the study of Hamiltonian paths"],"prefix":"10.1142","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4934-4571","authenticated-orcid":false,"given":"P.","family":"Renjith","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Information Technology, Design and Manufacturing Kurnool, Andhra Pradesh, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Sadagopan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Information Technology, Design and Manufacturing Kancheepuram, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,8,27]]},"reference":[{"issue":"2","key":"S1793830922501130BIB001","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0012-365X(91)90367-B","volume":"89","author":"Ainouche A.","year":"1991","journal-title":"Discrete Math."},{"issue":"2","key":"S1793830922501130BIB002","first-page":"73","volume":"3","author":"Akiyama T.","year":"1980","journal-title":"J. Inf. Process."},{"issue":"4","key":"S1793830922501130BIB004","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(86)90135-3","volume":"23","author":"Bertossi A. A.","year":"1986","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"S1793830922501130BIB005","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(76)90078-9","volume":"15","author":"Bondy J. A.","year":"1976","journal-title":"Discrete Math."},{"key":"S1793830922501130BIB006","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"Bondy J. A.","year":"1976"},{"issue":"1","key":"S1793830922501130BIB007","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0012-365X(01)00325-9","volume":"251","author":"Broersma H. J.","year":"2002","journal-title":"Discrete Math."},{"key":"S1793830922501130BIB008","first-page":"181","volume-title":"Contemporary Methods in Graph Theory","author":"Broersma H. J.","year":"1990"},{"issue":"1","key":"S1793830922501130BIB009","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0012-365X(98)00334-3","volume":"196","author":"Brousek J.","year":"1999","journal-title":"Discrete Math."},{"issue":"1","key":"S1793830922501130BIB010","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1111\/j.1749-6632.1979.tb32783.x","volume":"319","author":"Chartrand G.","year":"1979","journal-title":"Ann. N. Y. Acad. Sci."},{"issue":"2","key":"S1793830922501130BIB011","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0095-8956(72)90020-2","volume":"12","author":"Chv\u00e1tal V.","year":"1972","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"S1793830922501130BIB012","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(72)90079-9","volume":"2","author":"Chv\u00e1tal V.","year":"1972","journal-title":"Discrete Math."},{"issue":"1","key":"S1793830922501130BIB013","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0012-365X(95)00330-Y","volume":"169","author":"Collins K. L.","year":"1997","journal-title":"Discrete Math."},{"issue":"1","key":"S1793830922501130BIB014","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"3","author":"Dirac G. A.","year":"1952","journal-title":"Proc. Lond. Math. Soc."},{"issue":"2","key":"S1793830922501130BIB015","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0166-218X(92)00171-H","volume":"50","author":"Dorninger D.","year":"1994","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"S1793830922501130BIB016","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0012-365X(96)00147-1","volume":"173","author":"Faudree R. J.","year":"1997","journal-title":"Discrete Math."},{"issue":"2","key":"S1793830922501130BIB017","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/1097-0118(200010)35:2<69::AID-JGT1>3.0.CO;2-I","volume":"35","author":"Faudree R. J.","year":"2000","journal-title":"J. Graph Theory"},{"issue":"1","key":"S1793830922501130BIB018","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(89)90060-9","volume":"47","author":"Faudree R. J.","year":"1989","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"S1793830922501130BIB019","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1002\/jgt.10084","volume":"42","author":"Faudree R. J.","year":"2003","journal-title":"J. Graph Theory"},{"issue":"4","key":"S1793830922501130BIB020","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"Garey M. R.","year":"1976","journal-title":"SIAM J. Comput."},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","year":"1980","author":"Golumbic M. C.","key":"S1793830922501130BIB021"},{"key":"S1793830922501130BIB022","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0095-8956(74)90061-6","volume":"16","author":"Goodman S. E.","year":"1974","journal-title":"J. Combin. Theory Ser. B"},{"issue":"24","key":"S1793830922501130BIB023","doi-asserted-by":"crossref","first-page":"6166","DOI":"10.1016\/j.disc.2007.11.040","volume":"308","author":"Gordon V. S.","year":"2008","journal-title":"Discrete Math."},{"issue":"2","key":"S1793830922501130BIB024","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/jgt.3190150204","volume":"15","author":"Gould R. J.","year":"1991","journal-title":"J. Graph Theory"},{"issue":"1","key":"S1793830922501130BIB025","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/s00373-002-0492-x","volume":"19","author":"Gould R. J.","year":"2003","journal-title":"Graphs Combin."},{"key":"S1793830922501130BIB026","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0012-365X(82)90216-3","volume":"42","author":"Gould R. J.","year":"1982","journal-title":"Discrete Math."},{"issue":"1","key":"S1793830922501130BIB027","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/j.tcs.2005.04.009","volume":"341","author":"Hung R. W.","year":"2005","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"S1793830922501130BIB028","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1016\/j.aml.2010.11.030","volume":"24","author":"Hung R. W.","year":"2011","journal-title":"Appl. Math. Lett."},{"key":"S1793830922501130BIB029","first-page":"18","volume-title":"Proc. Intl. Conf. Engg. Computer Scientists","author":"Hung R. W.","year":"2009"},{"issue":"18","key":"S1793830922501130BIB030","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1016\/j.ipl.2009.07.010","volume":"109","author":"Ibarra L.","year":"2009","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"S1793830922501130BIB031","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.ejor.2006.05.009","volume":"180","author":"Irina G.","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"S1793830922501130BIB032","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","year":"1972"},{"issue":"4","key":"S1793830922501130BIB033","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"Keil J. M.","year":"1985","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"S1793830922501130BIB034","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1002\/(SICI)1097-0118(199909)32:1<17::AID-JGT2>3.0.CO;2-G","volume":"32","author":"Kierstead H. A.","year":"1999","journal-title":"J. Graph Theory"},{"issue":"9","key":"S1793830922501130BIB035","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.2307\/2313617","volume":"74","author":"Lindgren W. F.","year":"1967","journal-title":"Amer. Math. Monthly"},{"issue":"2","key":"S1793830922501130BIB036","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/0378-4371(76)90002-9","volume":"84","author":"Malakis A.","year":"1976","journal-title":"Physica A"},{"issue":"1","key":"S1793830922501130BIB037","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"Muller H.","year":"1996","journal-title":"Discrete Math."},{"issue":"4","key":"S1793830922501130BIB038","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0020-0190(89)90038-0","volume":"32","author":"Narasimhan G.","year":"1989","journal-title":"Inform. Process. Lett."},{"key":"S1793830922501130BIB039","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1090\/S0002-9939-1966-0188103-0","volume":"17","author":"Nash-Williams C. S. J. A.","year":"1966","journal-title":"Proc. Amer. Math. Soc."},{"issue":"8","key":"S1793830922501130BIB040","doi-asserted-by":"crossref","first-page":"611","DOI":"10.2307\/2309119","volume":"65","author":"Newman D. J.","year":"1958","journal-title":"Amer. Math. Monthly"},{"issue":"1","key":"S1793830922501130BIB041","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/(SICI)1097-0118(199701)24:1<45::AID-JGT6>3.0.CO;2-J","volume":"24","author":"Ng L.","year":"1997","journal-title":"J. Graph Theory"},{"issue":"1","key":"S1793830922501130BIB042","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2307\/2308928","volume":"67","author":"Ore O.","year":"1960","journal-title":"Amer. Math. Monthly"},{"issue":"3","key":"S1793830922501130BIB043","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","volume":"87","author":"Panda B. S.","year":"2003","journal-title":"Inform. Process. Lett."},{"issue":"6","key":"S1793830922501130BIB044","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1137\/0221061","volume":"21","author":"Shih W. K.","year":"1992","journal-title":"SIAM J. Comput."},{"issue":"1","key":"S1793830922501130BIB045","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0012-365X(74)90074-0","volume":"9","author":"Thomassen C.","year":"1974","journal-title":"Discrete Math."},{"volume-title":"Introduction to Graph Theory","year":"2003","author":"West D. B.","key":"S1793830922501130BIB046"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830922501130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T10:34:41Z","timestamp":1682850881000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S1793830922501130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,27]]},"references-count":45,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.1142\/S1793830922501130"],"URL":"https:\/\/doi.org\/10.1142\/s1793830922501130","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2022,8,27]]},"article-number":"2250113"}}