{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T18:18:48Z","timestamp":1770229128483,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2023,8]]},"DOI":"10.1007\/s10878-023-01076-9","type":"journal-article","created":{"date-parts":[[2023,8,14]],"date-time":"2023-08-14T19:23:17Z","timestamp":1692040997000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Maximum dissociation sets in subcubic trees"],"prefix":"10.1007","volume":"46","author":[{"given":"Lei","family":"Zhang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7667-2116","authenticated-orcid":false,"given":"Jianhua","family":"Tu","sequence":"additional","affiliation":[]},{"given":"Chunlin","family":"Xin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,14]]},"reference":[{"key":"1076_CR1","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s13119-011-0002-7","volume":"1","author":"HB Acharya","year":"2012","unstructured":"Acharya HB, Choi T, Bazzi RA, Gouda MG (2012) The $$k$$-observer problem in computer networks. Networking Sci. 1:15\u201322","journal-title":"Networking Sci."},{"issue":"12","key":"1076_CR2","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.tcs.2007.09.013","volume":"389","author":"VE Alekseev","year":"2007","unstructured":"Alekseev VE, Boliac R, Korobitsyn DV, Lozin VV (2007) NP-hard graph problems and boundary classes of graphs. Theoret. Comput. Sci. 389(12):219\u2013236","journal-title":"Theoret. Comput. Sci."},{"key":"1076_CR3","doi-asserted-by":"publisher","first-page":"934","DOI":"10.1016\/j.disc.2018.11.025","volume":"342","author":"JD Alvarado","year":"2019","unstructured":"Alvarado JD, Dantas S, Mohr E, Rautenbach D (2019) On the maximum number of minimum dominating sets in forests. Discrete Math. 342:934\u2013942","journal-title":"Discrete Math."},{"key":"1076_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"JA Bondy","year":"2008","unstructured":"Bondy JA, Murty USR (2008) Graph Theory. Springer, New York"},{"issue":"12","key":"1076_CR5","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar B, Kardo F, Katreni J, Semaniin G (2011) Minimum $$k$$-path vertex cover. Discrete Appl. Math. 159(12):1189\u20131195","journal-title":"Discrete Appl. Math."},{"key":"1076_CR6","first-page":"273","volume":"35","author":"D Br\u00f3d","year":"2006","unstructured":"Br\u00f3d D, Skupie\u0144 Z (2006) Trees with extremal numbers of dominating sets. Australas. J. Combin. 35:273\u2013290","journal-title":"Australas. J. Combin."},{"issue":"2\u20133","key":"1076_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10107-005-0649-5","volume":"105","author":"K Cameron","year":"2006","unstructured":"Cameron K, Hell P (2006) Independent packings in structured graphs. Math. Program. 105(2\u20133):201\u2013213","journal-title":"Math. Program."},{"key":"1076_CR8","doi-asserted-by":"publisher","first-page":"1537","DOI":"10.1016\/j.disc.2015.12.030","volume":"339","author":"S Connolly","year":"2016","unstructured":"Connolly S, Gabor Z, Godbole A, Kay B, Kelly T (2016) Bounds on the maximum number of minimum dominating sets. Discrete Math. 339:1537\u20131542","journal-title":"Discrete Math."},{"key":"1076_CR9","doi-asserted-by":"publisher","first-page":"1580","DOI":"10.1137\/20M1375048","volume":"51","author":"A Conte","year":"2022","unstructured":"Conte A, Marino A, Grossi R, Uno T, Versari L (2022) Proximity search for maximal subgraph enumeration. SIAM J. Comput. 51:1580\u20131625","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1076_CR10","first-page":"29","volume":"3","author":"T Derikvand","year":"2014","unstructured":"Derikvand T, Oboudi MR (2014) On the number of maximum independent sets of graphs. Transactions on Combin. 3(1):29\u201336","journal-title":"Transactions on Combin."},{"key":"1076_CR11","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/11602613_58","volume":"3827","author":"FV Fomin","year":"2005","unstructured":"Fomin FV, Grandoni F, Pyatkin AV, Stepanov AA (2005) Bounding the number of minimal dominating sets: a measure and conquer approach. Lecture Notes in Comput. Sci. 3827:573\u2013582","journal-title":"Lecture Notes in Comput. Sci."},{"key":"1076_CR12","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1002\/jgt.3190110403","volume":"11","author":"Z F\u00fcredi","year":"1987","unstructured":"F\u00fcredi Z (1987) The number of maximal independent sets in connected graphs. J. Graph Theory 11:463\u2013470","journal-title":"J. Graph Theory"},{"key":"1076_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0012-365X(88)90114-8","volume":"68","author":"JR Griggs","year":"1988","unstructured":"Griggs JR, Grinstead CM, Guichard DR (1988) The number of maximal independent sets in a connected graph. Discrete Math. 68:211\u2013220","journal-title":"Discrete Math."},{"key":"1076_CR14","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1002\/net.20318","volume":"54","author":"F Havet","year":"2009","unstructured":"Havet F, Kang RJ, Sereni JS (2009) Improper colouring of unit disk graphs. Networks. 54:150\u2013164","journal-title":"Networks."},{"key":"1076_CR15","doi-asserted-by":"publisher","first-page":"685","DOI":"10.11650\/twjm\/1500407302","volume":"4","author":"MJ Jou","year":"2000","unstructured":"Jou MJ, Chang GJ (2000) The number of maximum independent sets in graphs. Taiwan. J. Math. 4:685\u2013695","journal-title":"Taiwan. J. Math."},{"key":"1076_CR16","doi-asserted-by":"publisher","first-page":"7009","DOI":"10.1016\/j.tcs.2011.09.009","volume":"412","author":"F Kardo\u0161","year":"2011","unstructured":"Kardo\u0161 F, Katreni\u010d J, Schiermeyer I (2011) On computing the minium 3-path vertex cover and dissociation number of graphs. Theoret. Comput. Sci. 412:7009\u20137017","journal-title":"Theoret. Comput. Sci."},{"key":"1076_CR17","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.ipl.2015.12.002","volume":"116","author":"J Katreni\u010d","year":"2016","unstructured":"Katreni\u010d J (2016) A faster FPT algorithm for 3-path vertex cover. Inform. Process. Lett. 116:273\u2013278","journal-title":"Inform. Process. Lett."},{"key":"1076_CR18","doi-asserted-by":"publisher","first-page":"3761","DOI":"10.1016\/j.disc.2007.07.079","volume":"308","author":"KM Koh","year":"2008","unstructured":"Koh KM, Goh CY, Dong FM (2008) The maximum number of maximal independent sets in unicyclic connected graphs. Discrete Math. 308:3761\u20133769","journal-title":"Discrete Math."},{"issue":"4","key":"1076_CR19","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1002\/jgt.3190170407","volume":"17","author":"J Liu","year":"1993","unstructured":"Liu J (1993) Maximal independent sets in bipartite graphs. J. Graph Theory 17(4):495\u2013507","journal-title":"J. Graph Theory"},{"key":"1076_CR20","doi-asserted-by":"publisher","first-page":"1729","DOI":"10.1007\/s00373-018-1969-6","volume":"34","author":"E Mohr","year":"2018","unstructured":"Mohr E, Rautenbach D (2018) On the maximum number of maximum independent sets. Graphs Combin. 34:1729\u20131740","journal-title":"Graphs Combin."},{"key":"1076_CR21","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1002\/jgt.22629","volume":"96","author":"E Mohr","year":"2021","unstructured":"Mohr E, Rautenbach D (2021) On the maximum number of maximum independent sets in connected graphs. J. Graph Theory 96:510\u2013521","journal-title":"J. Graph Theory"},{"key":"1076_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon JW, Moser L (1965) On cliques in graphs. Israel J. Math. 3:23\u201328","journal-title":"Israel J. Math."},{"issue":"13","key":"1076_CR23","doi-asserted-by":"publisher","first-page":"1352","DOI":"10.1016\/j.dam.2011.04.023","volume":"159","author":"Y Orlovich","year":"2011","unstructured":"Orlovich Y, Dolguib A, Finkec G, Gordond V, Wernere F (2011) The complexity of dissociation set problems in graphs. Discrete Appl. Math. 159(13):1352\u20131366","journal-title":"Discrete Appl. Math."},{"key":"1076_CR24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1137\/0401012","volume":"1","author":"BE Sagan","year":"1988","unstructured":"Sagan BE (1988) A note on independent sets in trees. SIAM J. Discrete Math. 1:105\u2013108","journal-title":"SIAM J. Discrete Math."},{"key":"1076_CR25","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1002\/jgt.20186","volume":"53","author":"BE Sagan","year":"2006","unstructured":"Sagan BE, Vatter VR (2006) Maximal and maximum independent sets in graphs with at most $$r$$ cycles. J. Graph Theory 53:283\u2013314","journal-title":"J. Graph Theory"},{"key":"1076_CR26","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama S, Ide M, Ariyoshi H, Shirakawa I (1977) A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6:505\u2013517","journal-title":"SIAM J. Comput."},{"key":"1076_CR27","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"JH Tu","year":"2011","unstructured":"Tu JH, Zhou WL (2011) A primal-dual approximation algorithm for the vertex cover $$P_3$$ problem. Theoret. Comput. Sci. 412:7044\u20137048","journal-title":"Theoret. Comput. Sci."},{"key":"1076_CR28","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1002\/jgt.22627","volume":"96","author":"JH Tu","year":"2021","unstructured":"Tu JH, Zhang ZP, Shi YT (2021) The maximum number of maximum dissociation sets in trees. J. Graph Theory 96:472\u2013489","journal-title":"J. Graph Theory"},{"key":"1076_CR29","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1137\/0607015","volume":"7","author":"HS Wilf","year":"1986","unstructured":"Wilf HS (1986) The number of maximal independent sets in a tree. SIAM J. Alg. Discrete Methods 7:125\u2013130","journal-title":"SIAM J. Alg. Discrete Methods"},{"key":"1076_CR30","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2016.04.043","volume":"657","author":"M Xiao","year":"2017","unstructured":"Xiao M, Kou S (2017) Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems. Theoret. Comput. Sci. 657:86\u201397","journal-title":"Theoret. Comput. Sci."},{"key":"1076_CR31","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis M (1981) Node-deletion problems on bipartite graphs. SIAM J. Comput. 10:310\u2013327","journal-title":"SIAM J. Comput."},{"key":"1076_CR32","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1002\/jgt.3190150208","volume":"15","author":"J Zito","year":"1991","unstructured":"Zito J (1991) The structure and maximum number of maximum independent sets in trees. J. Graph Theory 15:207\u2013221","journal-title":"J. Graph Theory"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01076-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-023-01076-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01076-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T10:13:08Z","timestamp":1692785588000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-023-01076-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["1076"],"URL":"https:\/\/doi.org\/10.1007\/s10878-023-01076-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8]]},"assertion":[{"value":"1 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2023","order":2,"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 relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"8"}}