{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T00:31:57Z","timestamp":1716337917750},"reference-count":7,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2006,10,5]],"date-time":"2006-10-05T00:00:00Z","timestamp":1160006400000},"content-version":"vor","delay-in-days":6152,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1989,12]]},"abstract":"Abstract<\/jats:title>For a connected graph G<\/jats:italic> let L<\/jats:italic>(G) denote the maximum number of leaves in any spanning tree of G.<\/jats:italic> We give a simple construction and a complete proof of a result of Storer that if G<\/jats:italic> is a connected cubic graph on n<\/jats:italic> vertices, then L<\/jats:italic>(G) \u2a7e [(n<\/jats:italic>\/4) + 2], and this is best possible for all (even) n.<\/jats:italic> The main idea is to count the number of \u201cdead leaves\u201d as the tree is being constructed. This method of amortized analysis is used to prove the new result that if G<\/jats:italic> is also 3\u2010connected, then L<\/jats:italic>(G) \u2a7e [(n<\/jats:italic>\/3) + (4\/3)], which is best possible for many n.<\/jats:italic> This bound holds more generally for any connected cubic graph that contains no subgraph K<\/jats:italic>4<\/jats:sub> \u2010 e<\/jats:italic>. The proof is rather elaborate since several reducible configurations need to be eliminated before proceeding with the many tricky cases in the construction.<\/jats:p>","DOI":"10.1002\/jgt.3190130604","type":"journal-article","created":{"date-parts":[[2007,6,8]],"date-time":"2007-06-08T19:49:46Z","timestamp":1181332186000},"page":"669-695","source":"Crossref","is-referenced-by-count":41,"title":["Spanning trees with many leaves in cubic graphs"],"prefix":"10.1002","volume":"13","author":[{"given":"Jerrold R.","family":"Griggs","sequence":"first","affiliation":[]},{"given":"Daniel J.","family":"Kleitman","sequence":"additional","affiliation":[]},{"given":"Aditya","family":"Shastri","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,5]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90003-5"},{"key":"e_1_2_1_3_2","unstructured":"J. R.GriggsandM.Wu Spanning trees with many leaves in graphs of minimum degree 4 or 5 submitted (1989)."},{"key":"e_1_2_1_4_2","unstructured":"D. J.KleitmanandD. B.West Spanning trees with many leaves submitted (1988)."},{"key":"e_1_2_1_5_2","unstructured":"N.Linial personal communication (1988)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90141-1"},{"key":"e_1_2_1_7_2","unstructured":"V. K.Wei A lower bound on the stability number of a simple graph. Bell Laboratories Technical Memorandum 81\u20131217\u20139 (1981)."},{"key":"e_1_2_1_8_2","unstructured":"M.Wu personal communication (1988)."}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190130604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190130604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T02:57:26Z","timestamp":1697943446000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190130604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":7,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,12]]}},"alternative-id":["10.1002\/jgt.3190130604"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190130604","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}