{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T18:47:45Z","timestamp":1771354065350,"version":"3.50.1"},"reference-count":195,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2011,1]]},"DOI":"10.1007\/s00373-010-0973-2","type":"journal-article","created":{"date-parts":[[2010,8,31]],"date-time":"2010-08-31T00:33:27Z","timestamp":1283214807000},"page":"1-26","source":"Crossref","is-referenced-by-count":88,"title":["Spanning Trees: A Survey"],"prefix":"10.1007","volume":"27","author":[{"given":"Kenta","family":"Ozeki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoki","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,9,1]]},"reference":[{"key":"973_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01787474","volume":"6","author":"N. Alon","year":"1990","unstructured":"Alon N.: Transversal numbers of uniform hypergraphs. Graphs Combin. 6, 1\u20134 (1990)","journal-title":"Graphs Combin."},{"key":"973_CR2","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/978-3-540-73420-8_32","volume":"4596","author":"N. Alon","year":"2007","unstructured":"Alon N., Fomin F.V., Gutin G., Krivelevich M., Saurabh S.: Parameterized algorithms for directed maximum leaf problems. Lect. Notes Comput. Sci. 4596, 352\u2013362 (2007)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR3","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-540-77050-3_26","volume":"4855","author":"N. Alon","year":"2007","unstructured":"Alon N., Fomin F.V., Gutin G., Krivelevich M., Saurabh S.: Better algorithms and bounds for directed maximum leaf problems. Lect. Notes Comput. Sci. 4855, 316\u2013327 (2007)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR4","unstructured":"Alon, N., Wormald, N.: High degree graphs contain large-star factors. arXiv:math.CO.0810.2053v1"},{"key":"973_CR5","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1006\/jctb.1996.0056","volume":"68","author":"D. Archedeacon","year":"1996","unstructured":"Archedeacon D., Hartsfield N., Little C.H.C.: Nonhamiltonian triangulations with large connectivity and representativity. J. Combin. Theory Ser. B 68, 45\u201355 (1996)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR6","doi-asserted-by":"crossref","first-page":"2817","DOI":"10.1016\/j.disc.2006.05.024","volume":"306","author":"T. Atajan","year":"2006","unstructured":"Atajan T., Yong X., Inaba H.: Further analysis of the number of spanning trees in circulant graphs. Discrete Math. 306, 2817\u20132827 (2006)","journal-title":"Discrete Math."},{"key":"973_CR7","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s003730050027","volume":"14","author":"M. Aung","year":"1998","unstructured":"Aung M., Kyaw A.: Maximal trees with bounded maximum degree in a graph. Graphs Combin. 14, 209\u2013221 (1998)","journal-title":"Graphs Combin."},{"key":"973_CR8","doi-asserted-by":"crossref","first-page":"535","DOI":"10.4153\/CJM-1960-047-1","volume":"12","author":"T.I. Austin","year":"1960","unstructured":"Austin T.I.: The enumeration of point labelled chromatic graphs and trees. Can. J. Math. 12, 535\u2013545 (1960)","journal-title":"Can. J. Math."},{"key":"973_CR9","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/j.disc.2005.08.001","volume":"301","author":"C.S. Babu","year":"2005","unstructured":"Babu C.S., Diwan A.A.: Degree conditions for forests in graphs. Discrete Math. 301, 228\u2013231 (2005)","journal-title":"Discrete Math."},{"key":"973_CR10","doi-asserted-by":"crossref","first-page":"731","DOI":"10.4153\/CJM-1966-073-4","volume":"18","author":"D.W. Barnette","year":"1966","unstructured":"Barnette D.W.: Trees in polyhedral graphs. Can. J. Math 18, 731\u2013736 (1966)","journal-title":"Can. J. Math"},{"key":"973_CR11","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF02808218","volume":"79","author":"D.W. Barnette","year":"1992","unstructured":"Barnette D.W.: 3-trees in polyhedral maps. Isr. J. Math 79, 251\u2013256 (1992)","journal-title":"Isr. J. Math"},{"key":"973_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-006-0649-0","volume":"22","author":"D. Bauer","year":"2006","unstructured":"Bauer D., Broersma H., Schmeichel E.: Toughness in graphs\u2014a survey. Graphs Combin. 22, 1\u201335 (2006)","journal-title":"Graphs Combin."},{"key":"973_CR13","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0166-218X(99)00141-9","volume":"99","author":"D. Bauer","year":"2000","unstructured":"Bauer D., Broersma H., Veldman H.J.: Not every 2-tough graph is hamiltonian. Discrete Appl. Math. 99, 317\u2013321 (2000)","journal-title":"Discrete Appl. Math."},{"key":"973_CR14","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0012-365X(91)90468-H","volume":"96","author":"D. Bauer","year":"1991","unstructured":"Bauer D., Fan G., Veldman H.J.: Hamiltonian properties of graphs with large neighborhood unions. Discrete Math. 96, 33\u201349 (1991)","journal-title":"Discrete Math."},{"key":"973_CR15","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539791197852","volume":"23","author":"J.-C. Bermond","year":"1994","unstructured":"Bermond J.-C., Fraigniaud P.: Broadcasting and gossiping in deBruijn networks. SIAM J. Comput. 23, 212\u2013225 (1994)","journal-title":"SIAM J. Comput."},{"key":"973_CR16","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/net.3230210204","volume":"21","author":"F. Boesch","year":"1991","unstructured":"Boesch F., Li X., SuLel C.: On the existence of uniformly most reliable networks. Networks 21, 181\u2013194 (1991)","journal-title":"Networks"},{"key":"973_CR17","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/S0012-365X(96)00306-8","volume":"170","author":"T. B\u00f6hme","year":"1997","unstructured":"B\u00f6hme T., Broersma H.J., G\u00f6bel F., Kostochka A.V., Stiebitz M.: Spanning trees with pairwise nonadjacent endvertices. Discrete Math. 170, 219\u2013222 (1997)","journal-title":"Discrete Math."},{"key":"973_CR18","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(76)90078-9","volume":"15","author":"A. Bondy","year":"1976","unstructured":"Bondy A., Chv\u00e1tal V.: A method in graph theory. Discrete Math. 15, 111\u2013135 (1976)","journal-title":"Discrete Math."},{"issue":"3","key":"973_CR19","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1137\/060664318","volume":"22","author":"P. Bonsma","year":"2008","unstructured":"Bonsma P.: Spanning trees with many leaves in graphs with minimum degree three. SIAM J. Discrete Math. 22(3), 920\u2013937 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"973_CR20","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/978-3-540-78773-0_46","volume":"4957","author":"P. Bonsma","year":"2008","unstructured":"Bonsma P., Zickfeld F.: Spanning trees with many leaves in graphs without diamonds and blossoms. Lect. Notes Comput. Sci. 4957, 531\u2013543 (2008)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR21","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1007\/978-3-540-92248-3_7","volume":"5344","author":"P. Bonsma","year":"2008","unstructured":"Bonsma P., Zickfeld F.: A 3\/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. Lect. Notes Comput. Sci. 5344, 66\u201377 (2008)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR22","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/jctb.1994.1030","volume":"61","author":"S. Brandt","year":"1994","unstructured":"Brandt S.: Subtrees and subforests of graphs. J. Combin. Theory Ser. B 61, 63\u201370 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR23","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1002\/(SICI)1097-0118(199612)23:4<421::AID-JGT11>3.0.CO;2-F","volume":"23","author":"M.F. Bridgland","year":"1996","unstructured":"Bridgland M.F., Jamison R.E., Zito J.S.: The spanning trees forced by the path and the star. J. Graph Theory 23, 421\u2013441 (1996)","journal-title":"J. Graph Theory"},{"key":"973_CR24","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1002\/(SICI)1097-0037(200001)35:1<26::AID-NET3>3.0.CO;2-M","volume":"35","author":"H. Broersma","year":"2000","unstructured":"Broersma H., Koppius O., Tuinstra H., Huck A., Kloks T., Kratsch D., M\u00fcller H.: Degree- preserving trees. Networks 35, 26\u201339 (2000)","journal-title":"Networks"},{"key":"973_CR25","first-page":"225","volume":"43","author":"H.J. Broersma","year":"1996","unstructured":"Broersma H.J., Li X.: The connectivity of the leaf-exchange spanning tree graph of a graph. Ars Combin. 43, 225\u2013231 (1996)","journal-title":"Ars Combin."},{"key":"973_CR26","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1002\/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W","volume":"29","author":"H. Broersma","year":"1998","unstructured":"Broersma H., Tuinstra H.: Independence trees and Hamilton cycles. J. Graph Theory 29, 227\u2013237 (1998)","journal-title":"J. Graph Theory"},{"key":"973_CR27","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0166-218X(96)00045-5","volume":"74","author":"L. Cai","year":"1997","unstructured":"Cai L.: On spanning 2-trees in a graph. Discrete Appl. Math. 74, 203\u2013216 (1997)","journal-title":"Discrete Appl. Math."},{"key":"973_CR28","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0166-218X(02)00417-1","volume":"131","author":"L. Cai","year":"2003","unstructured":"Cai L.: The complexity of the locally connected spanning tree problem. Discrete Appl. Math. 131, 63\u201375 (2003)","journal-title":"Discrete Appl. Math."},{"key":"973_CR29","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1002\/jgt.3190150103","volume":"15","author":"Y. Caro","year":"1991","unstructured":"Caro Y., Krasikov I., Roditty Y.: On the largest tree of given maximum degree in a connected graph. J. Graph Theory 15, 7\u201313 (1991)","journal-title":"J. Graph Theory"},{"key":"973_CR30","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1137\/S0895480199353780","volume":"13","author":"Y. Caro","year":"2000","unstructured":"Caro Y., West D.B., Yuster R.: Connected domination and spanning trees with many leaves. SIAM J. Discrete Math. 13, 202\u2013211 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"973_CR31","unstructured":"Catlin, P.A.: Edge-connectivity and edge-disjoint spanning trees (2001, preprint). http:\/\/www.math.wvu.edu\/~hjlai\/Pdf\/Catlin_Pdf\/Catlin49a.pdf"},{"key":"973_CR32","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0166-218X(92)90002-R","volume":"40","author":"P.A. Catlin","year":"1992","unstructured":"Catlin P.A., Grossman J.W., Hobbs A.M., Lai H.J.: Fractional arboricity, strength, and principal partitions in graphs and matroids. Discrete Appl. Math. 40, 285\u2013302 (1992)","journal-title":"Discrete Appl. Math."},{"key":"973_CR33","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1016\/j.disc.2007.11.056","volume":"309","author":"P.A. Catlin","year":"2009","unstructured":"Catlin P.A., Lai H.J., Shao Y.: Edge-connectivity and edge-disjoint spanning trees. Discrete Math. 309, 1033\u20131040 (2009)","journal-title":"Discrete Math."},{"key":"973_CR34","first-page":"376","volume":"23","author":"A. Cayley","year":"1889","unstructured":"Cayley A.: A theorem on trees. Q. J. Math. 23, 376\u2013378 (1889)","journal-title":"Q. J. Math."},{"key":"973_CR35","doi-asserted-by":"crossref","unstructured":"Chen, G., Egawa, Y., Kawarabayashi, K., Mohar, B., Ota, K.: Toughness of K a,t -minor-free graphs (2010, submitted)","DOI":"10.37236\/635"},{"key":"973_CR36","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0012-365X(93)90147-L","volume":"111","author":"C.C. Chen","year":"1993","unstructured":"Chen C.C., Koh K.M., Peng Y.H.: On the higher-order edge toughness of a graph. Discrete Math. 111, 113\u2013123 (1993)","journal-title":"Discrete Math."},{"key":"973_CR37","first-page":"157","volume":"22","author":"Z.H. Chen","year":"1996","unstructured":"Chen Z.H., Lai H.J.: The higher-order edge-toughness of a graph and truncated uniformly dense matroids. J. Combin. Math. Combin. Comput. 22, 157\u2013160 (1996)","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"973_CR38","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.disc.2003.12.006","volume":"282","author":"X. Chen","year":"2004","unstructured":"Chen X., Lin Q., Zhang F.: The number of spanning trees in odd valent circulant graphs. Discrete Math. 282, 69\u201379 (2004)","journal-title":"Discrete Math."},{"key":"973_CR39","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/S0095-8956(81)80028-7","volume":"31","author":"C. Cheng","year":"1981","unstructured":"Cheng C.: Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimization design theory. J. Combin. Theory Ser. B 31, 240\u2013248 (1981)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR40","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1016\/0196-6774(88)90015-6","volume":"9","author":"J. Cheriyan","year":"1988","unstructured":"Cheriyan J., Maheshwari S.: Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms 9, 507\u2013537 (1988)","journal-title":"J. Algorithms"},{"key":"973_CR41","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0012-365X(93)90343-R","volume":"117","author":"S. Choi","year":"1993","unstructured":"Choi S., Guan P.: A spanning tree of the 2 m -dimensional hypercube with maximum number of degree-preserving vertices. Discrete Math. 117, 275\u2013277 (1993)","journal-title":"Discrete Math."},{"key":"973_CR42","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V. Chv\u00e0tal","year":"1973","unstructured":"Chv\u00e0tal V.: Tough graphs and hamiltonian circuits. Discerete Math. 5, 215\u2013228 (1973)","journal-title":"Discerete Math."},{"key":"973_CR43","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1002\/jgt.3190010118","volume":"1","author":"V. Chv\u00e0tal","year":"1977","unstructured":"Chv\u00e0tal V.: Tree\u2014complete graph Ramsey numbers. J. Graph Theory 1, 93 (1977)","journal-title":"J. Graph Theory"},{"key":"973_CR44","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(72)90079-9","volume":"2","author":"V. Chv\u00e1tal","year":"1972","unstructured":"Chv\u00e1tal V., Erd\u0151s P.: A note on hamiltonian circuits. Discrete Math. 2, 111\u2013113 (1972)","journal-title":"Discrete Math."},{"key":"973_CR45","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/978-3-540-77918-6_15","volume":"4927","author":"J.R. Correa","year":"2008","unstructured":"Correa J.R., Fernandes C.G., Matamala M., Wakabayashi Y.: A 5\/3-approximation for finding spanning trees with many leaves in cubic graphs. Lect. Notes Comput. Sci. 4927, 184\u2013192 (2008)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR46","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1109\/TCT.1966.1082546","volume":"13","author":"R.L. Cummins","year":"1966","unstructured":"Cummins R.L.: Hamilton circuits in tree graphs. IEEE Trans. Circuit Theory 13, 82\u201390 (1966)","journal-title":"IEEE Trans. Circuit Theory"},{"key":"973_CR47","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/3828.3829","volume":"32","author":"W.H. Cunningham","year":"1985","unstructured":"Cunningham W.H.: Optimal attack and reinforcement of a network. J. Assoc. Comput. Mach. 32, 549\u2013561 (1985)","journal-title":"J. Assoc. Comput. Mach."},{"key":"973_CR48","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1137\/S0895480103434592","volume":"19","author":"S. Curran","year":"2005","unstructured":"Curran S., Lee O., Yu X.: Chain decompositions of 4-connected graphs. SIAM J. Discrete Math. 19, 848\u2013880 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"973_CR49","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1137\/S0097539703436734","volume":"35","author":"S. Curran","year":"2006","unstructured":"Curran S., Lee O., Yu X.: Finding four independent trees. SIAM J. Comput. 35, 1023\u20131058 (2006)","journal-title":"SIAM J. Comput."},{"key":"973_CR50","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/S0895480103434580","volume":"19","author":"S. Curran","year":"2006","unstructured":"Curran S., Lee O., Yu X.: Nonseparating planar chains in 4-connected graphs. SIAM J. Discrete Math. 19, 399\u2013419 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"973_CR51","unstructured":"Cvetkovi\u010d, D., Doob, M., Sachs, H.: Spectra of graphs. In: Mathematics, vol. 87. Academic press, New York (1980)"},{"key":"973_CR52","doi-asserted-by":"crossref","first-page":"R33","DOI":"10.37236\/1577","volume":"8","author":"A. Czygrinow","year":"2001","unstructured":"Czygrinow A., Fan G., Hurlbert G., Kierstead H.A., Trotter W.T.: Spanning trees of bounded degree. Electron. J. Combin. 8, R33 (2001)","journal-title":"Electron. J. Combin."},{"key":"973_CR53","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0166-218X(02)00422-5","volume":"131","author":"E. Dahlhaus","year":"2003","unstructured":"Dahlhaus E., Dankelmann P., Goddard W., Swart H.C.: MAD trees and distance-hereditary graphs. Dicrete Appl. Math. 131, 151\u2013167 (2003)","journal-title":"Dicrete Appl. Math."},{"key":"973_CR54","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.ipl.2003.11.009","volume":"89","author":"E. Dahlhaus","year":"2004","unstructured":"Dahlhaus E., Dankelmann P., Ravi R.: A linear-time algorithm to compute a MAD tree of an interval graph. Inform. Process. Lett. 89, 255\u2013259 (2004)","journal-title":"Inform. Process. Lett."},{"key":"973_CR55","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L","volume":"33","author":"P. Dankelmann","year":"2000","unstructured":"Dankelmann P., Entringer R.: Average distance, minimum degree, and spanning trees. J. Graph Theory 33, 1\u201313 (2000)","journal-title":"J. Graph Theory"},{"key":"973_CR56","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0012-365X(00)00005-4","volume":"222","author":"P. Damaschke","year":"2000","unstructured":"Damaschke P.: Degree-preserving spanning trees in small-degree graphs. Discrete Math. 222, 51\u201360 (2000)","journal-title":"Discrete Math."},{"key":"973_CR57","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1007\/s00373-007-0758-4","volume":"23","author":"K.C. Das","year":"2007","unstructured":"Das K.C.: A sharp upper bounds for the number of spanning trees of a graph. Graphs Combin. 23, 625\u2013632 (2007)","journal-title":"Graphs Combin."},{"key":"973_CR58","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1002\/jgt.1013","volume":"37","author":"G. Ding","year":"2001","unstructured":"Ding G., Johnson T., Seymour P.: Spanning trees with many leaves. J. Graph Theory 37, 189\u2013197 (2001)","journal-title":"J. Graph Theory"},{"key":"973_CR59","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/s00373-007-0768-2","volume":"24","author":"Y. Egawa","year":"2008","unstructured":"Egawa Y., Matsuda H., Yamashita T., Yoshimoto K.: On a spanning tree with specified leaves. Graphs Combin. 24, 13\u201318 (2008)","journal-title":"Graphs Combin."},{"key":"973_CR60","unstructured":"Egawa, Y., Ozeki, K.: A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees (2010, submitted)"},{"key":"973_CR61","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0097-3165(86)90004-X","volume":"42","author":"O. E\u01e7ecio\u01e7lu","year":"1986","unstructured":"E\u01e7ecio\u01e7lu O., Remmel J.B.: Bijections for Cayley trees, spanning trees and their q-analogues. J. Combin. Theory Ser. A 42, 15\u201330 (1986)","journal-title":"J. Combin. Theory Ser. A"},{"key":"973_CR62","first-page":"225","volume":"100","author":"O. E\u01e7ecio\u01e7lu","year":"1994","unstructured":"E\u01e7ecio\u01e7lu O., Remmel J.B.: A bijection for spanning trees of complete multipartite graphs. Congr. Numer. 100, 225\u2013243 (1994)","journal-title":"Congr. Numer."},{"key":"973_CR63","first-page":"55","volume":"115","author":"M.N. Ellingham","year":"1996","unstructured":"Ellingham M.N.: Spanning paths, cycles and walks for graphs on surfaces. Congr. Numer. 115, 55\u201390 (1996)","journal-title":"Congr. Numer."},{"key":"973_CR64","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1006\/jctb.1994.1043","volume":"61","author":"M.N. Ellingham","year":"1994","unstructured":"Ellingham M.N., Gao Z.: Spanning trees in locally planar triangulations. J. Combin Theory Ser. B 61, 178\u2013198 (1994)","journal-title":"J. Combin Theory Ser. B"},{"key":"973_CR65","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1002\/jgt.10019","volume":"39","author":"M.N. Ellingham","year":"2002","unstructured":"Ellingham M.N., Nam Y., Voss H.-J.: Connected (g, f)-factor. J. Graph Theory 39, 62\u201375 (2002)","journal-title":"J. Graph Theory"},{"key":"973_CR66","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X","volume":"33","author":"M.N. Ellingham","year":"2000","unstructured":"Ellingham M.N., Zha X.: Toughness, trees, and walks. J. Graph Theory 33, 125\u2013137 (2000)","journal-title":"J. Graph Theory"},{"key":"973_CR67","unstructured":"Enomoto, H.: private communication"},{"key":"973_CR68","unstructured":"Enomoto, H., Ohnishi, Y., Ota, K.: Spanning trees with bounded total excess. Ars Combin (2010, to appear)"},{"key":"973_CR69","doi-asserted-by":"crossref","unstructured":"Enomoto, H., Ozeki, K.: The independence number condition for the existence of a spanning f-tree. J. Graph Thoery (2010, to appear)","DOI":"10.1002\/jgt.20471"},{"key":"973_CR70","first-page":"65","volume":"24","author":"R.C. Entringer","year":"1997","unstructured":"Entringer R.C.: Distance in graphs: trees. J. Combin. Math. Combin. Comput. 24, 65\u201384 (1997)","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"973_CR71","first-page":"71","volume":"17","author":"R.C. Entringer","year":"1996","unstructured":"Entringer R.C., Kleitman D.J., Sz\u00e9kely L.A.: A note on spanning trees with minimum average distance. Bull. Inst. Combim. Appl. 17, 71\u201378 (1996)","journal-title":"Bull. Inst. Combim. Appl."},{"key":"973_CR72","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications, pp. 29\u201336. Academic Press, New York (1964)","DOI":"10.4064\/cm-13-2-251-254"},{"key":"973_CR73","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0095-8956(82)90032-6","volume":"32","author":"P. Erd\u0151s","year":"1982","unstructured":"Erd\u0151s P., Faudree R.J., Rousseau C.C., Schelp R.H.: Graphs with certain families of spanning trees. J. Combin. Theory Ser. B 32, 162\u2013170 (1982)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR74","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF02024498","volume":"10","author":"P. Erd\u0151s","year":"1959","unstructured":"Erd\u0151s P., Gallai T.: On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hung. 10, 337\u2013356 (1959)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"973_CR75","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/S0012-365X(00)00092-3","volume":"223","author":"V. Estivill-Castro","year":"2000","unstructured":"Estivill-Castro V., Noy M., Urrutia J.: On the chromatic number of tree graphs. Discrete Math. 223, 363\u2013366 (2000)","journal-title":"Discrete Math."},{"key":"973_CR76","doi-asserted-by":"crossref","first-page":"3055","DOI":"10.1016\/j.disc.2007.03.018","volume":"307","author":"G. Fan","year":"2007","unstructured":"Fan G., Sun L.: The Erd\u0151s-S\u00f3s conjecture for spiders. Discrete Math. 307, 3055\u20133062 (2007)","journal-title":"Discrete Math."},{"key":"973_CR77","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF02761188","volume":"35","author":"R.J. Faudree","year":"1980","unstructured":"Faudree R.J., Rousseau C.C., Schelp R.H., Schuster S.: Panarboreal graphs. Isr. J. Math. 35, 177\u2013185 (1980)","journal-title":"Isr. J. Math."},{"key":"973_CR78","doi-asserted-by":"crossref","first-page":"255","DOI":"10.2298\/AADM0802255F","volume":"2","author":"L. Feng","year":"2008","unstructured":"Feng L., Yu G., Jiang Z., Ren L.: Sharp upper bounds for the number of spanning trees of a graph. Appl. Anal. Discrete Math. 2, 255\u2013259 (2008)","journal-title":"Appl. Anal. Discrete Math."},{"key":"973_CR79","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/net.10022","volume":"39","author":"M. Fischetti","year":"2002","unstructured":"Fischetti M., Lancia G., Serafini P.: Exact algorithms for minimum routing cost trees. Networks 39, 161\u2013173 (2002)","journal-title":"Networks"},{"key":"973_CR80","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(91)90094-I","volume":"90","author":"E. Flandrin","year":"1991","unstructured":"Flandrin E., Jung H.A., Li H.: Hamiltonism, degree sum and neighborhood intersections. Discrete Math. 90, 41\u201352 (1991)","journal-title":"Discrete Math."},{"key":"973_CR81","doi-asserted-by":"crossref","first-page":"2343","DOI":"10.1016\/j.disc.2007.04.071","volume":"308","author":"E. Flandrin","year":"2008","unstructured":"Flandrin E., Kaiser T., Ku\u017eel R., Li H., Ryj\u00e1\u010dek Z.: Neighborhood unions and extremal spanning trees. Discrete Math. 308, 2343\u20132350 (2008)","journal-title":"Discrete Math."},{"key":"973_CR82","first-page":"353","volume":"18","author":"A. Frank","year":"1976","unstructured":"Frank A., Gy\u00e0rf\u00e0s A.: How to orient the edges of a graph?. Colloq. Math. Soc. J\u00e0nos Bolyai 18, 353\u2013364 (1976)","journal-title":"Colloq. Math. Soc. J\u00e0nos Bolyai"},{"key":"973_CR83","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/S0166-218X(02)00463-8","volume":"131","author":"A. Frank","year":"2003","unstructured":"Frank A., Kir\u00e1ly T., Kriesell M.: On decomposing a hypergraph into k connected sub-hypergraphs. Discrete Appl. Math. 131, 373\u2013383 (2003)","journal-title":"Discrete Appl. Math."},{"key":"973_CR84","doi-asserted-by":"crossref","unstructured":"Fujisawa, J., Matsumura, H., Yamashita, T.: Degree bounded spanning trees. Graphs Combin. (2010, to appear)","DOI":"10.1007\/s00373-010-0941-x"},{"key":"973_CR85","doi-asserted-by":"crossref","unstructured":"Fujisawa, J., Saito, A., Schiermeyer, I.: Closure for spanning trees and distant area (2010, submitted)","DOI":"10.7151\/dmgt.1534"},{"key":"973_CR86","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1007\/978-3-540-77120-3_78","volume":"4835","author":"E.G. Fusco","year":"2007","unstructured":"Fusco E.G., Monti A.: Spanning trees with many leaves in regular bipartite graphs. Lect. Notes Comput. Sci. 4835, 904\u2013914 (2007)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR87","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979)"},{"key":"973_CR88","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1007\/3-540-45061-0_63","volume":"2719","author":"L. Gargano","year":"2003","unstructured":"Gargano L., Hammar M.: There are spanning spiders in dense graphs (and we know how to find them). Lect. Notes Comput. Sci. 2719, 802\u2013816 (2003)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR89","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.disc.2004.04.005","volume":"285","author":"L. Gargano","year":"2004","unstructured":"Gargano L., Hammar M., Hell P., Stacho L., Vaccaro U.: Spanning spiders and light-splitting switches. Discrete Math. 285, 83\u201395 (2004)","journal-title":"Discrete Math."},{"key":"973_CR90","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/3-540-45465-9_31","volume":"2380","author":"L. Gargano","year":"2002","unstructured":"Gargano L., Hell P., Stacho L., Vaccaro U.: Spanning trees with bounded number of branch vertices. Lect. Notes Comput. Sci. 2380, 355\u2013365 (2002)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR91","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/(SICI)1097-0037(199708)30:1<23::AID-NET3>3.0.CO;2-N","volume":"30","author":"B. Gilbert","year":"1997","unstructured":"Gilbert B., Myrvold W.: Maximizing spanning trees in almost complete graphs. Networks 30, 23\u201330 (1997)","journal-title":"Networks"},{"key":"973_CR92","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1002\/jgt.3190130604","volume":"13","author":"J.R. Griggs","year":"1989","unstructured":"Griggs J.R., Kleitman D.J., Shastri A.: Spanning trees with many leaves in cubic graphs. J. Graph Theory 13, 669\u2013695 (1989)","journal-title":"J. Graph Theory"},{"key":"973_CR93","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0012-365X(92)90331-9","volume":"104","author":"J.R. Griggs","year":"1992","unstructured":"Griggs J.R., Wu M.: Spanning trees in graphs of minimum degree 4 or 5. Discrete Math. 104, 167\u2013183 (1992)","journal-title":"Discrete Math."},{"key":"973_CR94","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0012-365X(76)80005-2","volume":"16","author":"G.R. Grimmett","year":"1976","unstructured":"Grimmett G.R.: An upper bound for the number of spanning trees of a graph. Discrete Math. 16, 323\u2013324 (1976)","journal-title":"Discrete Math."},{"key":"973_CR95","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0012-365X(88)90182-3","volume":"69","author":"R. Grone","year":"1988","unstructured":"Grone R., Merris R.: A bound for the complexity of a simple graph. Discrete Math. 69, 97\u201399 (1988)","journal-title":"Discrete Math."},{"key":"973_CR96","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(86)90023-7","volume":"41","author":"M.A. Gurgel","year":"1986","unstructured":"Gurgel M.A., Wakabayashi Y.: On k-leaf-connected graphs. J. Combin. Theory Ser. B 41, 1\u201316 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR97","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1109\/TCS.1983.1085385","volume":"30","author":"F. Harary","year":"1983","unstructured":"Harary F., Mokken R.J., Plantholt M.J.: Interpolation theorem for diameters of spanning trees. IEEE Trans. Circuits Syst. 30, 429\u2013432 (1983)","journal-title":"IEEE Trans. Circuits Syst."},{"key":"973_CR98","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0166-218X(00)00269-9","volume":"110","author":"T. Hasunuma","year":"2001","unstructured":"Hasunuma T., Nagamochi H.: Independent spanning trees with small depths in iterated line graphs. Discrete Appl. Math. 110, 189\u2013211 (2001)","journal-title":"Discrete Appl. Math."},{"key":"973_CR99","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/jgt.3190120110","volume":"12","author":"K. Heinrich","year":"1988","unstructured":"Heinrich K., Liu G.: A lower bound on the number of spanning trees with k end-vertices. J. Graph Theory 12, 95\u2013100 (1988)","journal-title":"J. Graph Theory"},{"key":"973_CR100","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01202468","volume":"10","author":"A. Huck","year":"1994","unstructured":"Huck A.: Independent trees in graphs. Graphs Combin. 10, 29\u201345 (1994)","journal-title":"Graphs Combin."},{"key":"973_CR101","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1002\/jgt.3190200212","volume":"20","author":"A. Huck","year":"1995","unstructured":"Huck A.: Disproof of a conjecture about independent spanning trees in k-connected directed graphs. J. Graph Theory 20, 235\u2013239 (1995)","journal-title":"J. Graph Theory"},{"key":"973_CR102","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0012-365X(98)00338-0","volume":"199","author":"A. Huck","year":"1999","unstructured":"Huck A.: Independent branching in acyclic digraphs. Discrete Math. 199, 245\u2013249 (1999)","journal-title":"Discrete Math."},{"key":"973_CR103","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s003730050041","volume":"15","author":"A. Huck","year":"1999","unstructured":"Huck A.: Independent trees in planar graphs independent trees. Graphs Combin. 15, 29\u201377 (1999)","journal-title":"Graphs Combin."},{"key":"973_CR104","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0890-5401(88)90016-8","volume":"79","author":"A. Itai","year":"1988","unstructured":"Itai A., Rodeh M.: The multi-tree approach to reliability in distributed networks. Inform. Comput. 79, 43\u201359 (1988)","journal-title":"Inform. Comput."},{"key":"973_CR105","unstructured":"Jackson, B.: Hamilton cycles in 7-connected line graphs (2010, preprint)"},{"key":"973_CR106","first-page":"135","volume":"2","author":"B. Jackson","year":"1990","unstructured":"Jackson B., Wormald N.C.: k-walks of graphs. Aust. J. Combin. 2, 135\u2013146 (1990)","journal-title":"Aust. J. Combin."},{"key":"973_CR107","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0095-8956(79)90057-1","volume":"26","author":"F. Jaeger","year":"1979","unstructured":"Jaeger F.: Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B 26, 205\u2013216 (1979)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR108","unstructured":"Jain, K., Mahdian, M., Salavatipour, M.R.: Packing Steiner trees. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 266\u2013274 (2003)"},{"key":"973_CR109","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1002\/net.3230080402","volume":"8","author":"D.S. Johnson","year":"1978","unstructured":"Johnson D.S., Lenstra J.K., Rinnooy-Kan A.H.: The complexity of the network design problem. Networks 8, 279\u2013285 (1978)","journal-title":"Networks"},{"key":"973_CR110","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.jctb.2005.04.003","volume":"95","author":"T. Jord\u00e1n","year":"2005","unstructured":"Jord\u00e1n T.: On the existence of k edge-disjoint 2-connected spanning subgraphs. J. Combin. Theory Ser. B 95, 257\u2013262 (2005)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR111","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0166-218X(01)00216-5","volume":"115","author":"A. Kaneko","year":"2001","unstructured":"Kaneko A.: Spanning trees with constraints on the leaf degree. Discrete Appl. Math. 115, 73\u201376 (2001)","journal-title":"Discrete Appl. Math."},{"key":"973_CR112","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/jgt.20221","volume":"55","author":"A. Kaneko","year":"2007","unstructured":"Kaneko A., Kano M., Suzuki K.: Spanning trees with leaf distance at least four. J. Graph Theory 55, 83\u201390 (2007)","journal-title":"J. Graph Theory"},{"key":"973_CR113","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1006\/jctb.1998.1895","volume":"76","author":"A. Kaneko","year":"1999","unstructured":"Kaneko A., Yoshimoto K.: The connectivities of leaf graphs of 2-connected graphs. J. Combin. Theory Ser. B 76, 155\u2013169 (1999)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR114","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/S0020-0190(00)00018-1","volume":"73","author":"A. Kaneko","year":"2000","unstructured":"Kaneko A., Yoshimoto K.: On spanning trees with restricted degrees. Inform. Process. Lett. 73, 163\u2013165 (2000)","journal-title":"Inform. Process. Lett."},{"key":"973_CR115","doi-asserted-by":"crossref","unstructured":"Kano, M., Kishimoto, H.: Spanning k-tree of n-connected graphs. Graphs Combin. (2010, to appear)","DOI":"10.1007\/s00373-011-1021-6"},{"key":"973_CR116","unstructured":"Kano, M., Kyaw, A., Matsuda, H., Ozeki, K., Saito, A., Yamashita, T.: Spanning trees with a bounded number of leaves in a claw-free graph (2010, submitted)"},{"key":"973_CR117","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0095-8956(03)00072-8","volume":"89","author":"K. Kawarabayashi","year":"2003","unstructured":"Kawarabayashi K., Nakamoto A., Ota K.: Subgraphs of graphs on surfaces with high representativity. J. Combin. Theory Ser. B 89, 207\u2013229 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR118","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<177::AID-RSA11>3.0.CO;2-L","volume":"9","author":"A. Kelmans","year":"1996","unstructured":"Kelmans A.: On graphs with the maximum number of spanning trees. Random Struct. Algorithms 9, 177\u2013192 (1996)","journal-title":"Random Struct. Algorithms"},{"key":"973_CR119","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0020-0190(92)90230-S","volume":"42","author":"B. Khuller","year":"1992","unstructured":"Khuller B., Schieber B.: On independent spanning trees. Inform. Process. Lett. 42, 321\u2013323 (1992)","journal-title":"Inform. Process. Lett."},{"key":"973_CR120","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"72","author":"G. Kirchhoff","year":"1847","unstructured":"Kirchhoff, G.: \u00dcber dieAufl\u00f6sung derGleichungen, aufwelcheman bei der Untersuchung der linearen Verteilung galvanischer Str\u00f6me gef\u00fchrt wird. Ann. Phys. Chem. 72, 497\u2013508 (1847)","journal-title":"Ann. Phys. Chem."},{"key":"973_CR121","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"D.J. Kleitman","year":"1991","unstructured":"Kleitman D.J., West D.B.: Spanning trees with many leaves. SIAM J. Discrete Math. 4, 99\u2013106 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"973_CR122","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-004-0587-7","volume":"21","author":"M. Kouider","year":"2005","unstructured":"Kouider M., Vestergaard P.D.: Connected factors in graphs\u2014a survey. Graphs Combin. 21, 1\u201326 (2005)","journal-title":"Graphs Combin."},{"key":"973_CR123","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0095-8956(02)00013-8","volume":"88","author":"M. Kriesell","year":"2003","unstructured":"Kriesell M.: Edge-disjoint trees containing some given vertices in a graph. J. Combin. Theory Ser. B 88, 53\u201365 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR124","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1002\/jgt.20389","volume":"62","author":"M. Kriesell","year":"2009","unstructured":"Kriesell M.: Edge disjoint Steiner trees in graphs without large bridges. J. Graph Theory 62, 188\u2013198 (2009)","journal-title":"J. Graph Theory"},{"key":"973_CR125","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s003730170059","volume":"17","author":"A. Kyaw","year":"2001","unstructured":"Kyaw A.: A sufficient condition for a graph to have a k-tree. Graphs Combin. 17, 113\u2013121 (2001)","journal-title":"Graphs Combin."},{"key":"973_CR126","doi-asserted-by":"crossref","first-page":"6146","DOI":"10.1016\/j.disc.2009.04.023","volume":"309","author":"A. Kyaw","year":"2009","unstructured":"Kyaw A.: Spanning trees with at most 3 leaves in K 1,4-free graphs. Discrete Math. 309, 6146\u20136148 (2009)","journal-title":"Discrete Math."},{"key":"973_CR127","unstructured":"Kyaw, A.: private communication"},{"key":"973_CR128","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s00493-007-0044-3","volume":"27","author":"L.C. Lau","year":"2007","unstructured":"Lau L.C.: An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica 27, 71\u201390 (2007)","journal-title":"Combinatorica"},{"key":"973_CR129","unstructured":"Lemke, P.: The maximum leaf spanning tree problem for cubic graphs is NP-complete. IMA Preprint Series, # 428 (1988)"},{"key":"973_CR130","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1109\/TCS.1987.1086107","volume":"34","author":"M. Lewinter","year":"1987","unstructured":"Lewinter M.: Interpolation theorem for the number of degree-preserving vertices of spanning trees. IEEE Trans. Circuits Syst. 34, 205 (1987)","journal-title":"IEEE Trans. Circuits Syst."},{"key":"973_CR131","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1016\/S0012-365X(99)90111-5","volume":"197\/198","author":"R.P. Lewis","year":"1999","unstructured":"Lewis R.P.: The number of spanning trees of a complete multipartite graph. Discrete Math. 197\/198, 537\u2013541 (1999)","journal-title":"Discrete Math."},{"key":"973_CR132","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0012-365X(03)00132-8","volume":"271","author":"X. Li","year":"2003","unstructured":"Li X., Neumann-Lara V., Rivera-Campo E.: On a tree graph defined by a set of cycles. Discrete Math. 271, 303\u2013310 (2003)","journal-title":"Discrete Math."},{"key":"973_CR133","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.ipl.2005.10.011","volume":"97","author":"P.C. Li","year":"2006","unstructured":"Li P.C., Toulouse M.: Variations of the maximum leaf spanning tree problem for bipartite graphs. Inform. Process. Lett. 97, 129\u2013132 (2006)","journal-title":"Inform. Process. Lett."},{"key":"973_CR134","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/j.disc.2006.06.026","volume":"307","author":"C.C. Lin","year":"2007","unstructured":"Lin C.C., Chang G.J., Chen G.H.: Locally connected spanning trees in strongly chordal graphs and proper circular graphs. Discrete Math. 307, 208\u2013215 (2007)","journal-title":"Discrete Math."},{"key":"973_CR135","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1002\/jgt.3190120318","volume":"12","author":"G.Z. Liu","year":"1988","unstructured":"Liu G.Z.: On connectivities of tree graphs. J. Graph Theory 12, 453\u2013459 (1988)","journal-title":"J. Graph Theory"},{"key":"973_CR136","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1007\/3-540-45749-6_60","volume":"2461","author":"K. Lory\u015b","year":"2002","unstructured":"Lory\u015b K., Zwo\u017aniak G.: Approximation algorithm for the maximum leaf spanning tree problem for cubic graphs. Lect. Notes Comput. Sci. 2461, 686\u2013697 (2002)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR137","unstructured":"Lu, H.I., Ravi, R.: The power of local optimization: approximation algorithms for maximum-leaf spanning tree. In: Proceedings of the Thirtieth Annual Allerton Conference on Communication, Control and Computing, pp. 533\u2013542 (1992)"},{"key":"973_CR138","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jagm.1998.0944","volume":"29","author":"H.I. Lu","year":"1998","unstructured":"Lu H.I., Ravi R.: Approximating maximum leaf spanning trees in almost linear time. J. Algorithms 29, 132\u2013141 (1998)","journal-title":"J. Algorithms"},{"key":"973_CR139","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/s00373-006-0660-5","volume":"22","author":"H. Matsuda","year":"2006","unstructured":"Matsuda H., Matsumura H.: On a k-tree containing specified leaves in a graph. Graphs Combin. 22, 371\u2013381 (2006)","journal-title":"Graphs Combin."},{"key":"973_CR140","unstructured":"Matsuda, H., Ozeki, K., Yamashita, T.: Spanning trees with a bounded number of branch vertices in a claw-free graph (2010, submitted)"},{"key":"973_CR141","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/jgt.3190080116","volume":"8","author":"M.M. Matthews","year":"1984","unstructured":"Matthews M.M., Sumner D.P.: Hamiltonian results in K 1,3-free graphs. J. Graph Theory 8, 139\u2013146 (1984)","journal-title":"J. Graph Theory"},{"key":"973_CR142","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0024-3795(94)90486-3","volume":"197\/198","author":"R. Merris","year":"1994","unstructured":"Merris R.: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197\/198, 143\u2013176 (1994)","journal-title":"Linear Algebra Appl."},{"key":"973_CR143","first-page":"310","volume":"1517","author":"K. Miura","year":"1998","unstructured":"Miura K., Takahashi D., Nakano S., Nishizeki T.: A linear-time algorithm to find four independent spanning trees in four-connected planar graphs. Graph Theor. Concepts Comput. Sci. 1517, 310\u2013323 (1998)","journal-title":"Graph Theor. Concepts Comput. Sci."},{"key":"973_CR144","unstructured":"Moon, J.W.: Counting Labelled Trees, Canadian Mathematical Monographs, No. 1, Canadian Mathematical Congress, Montreal (1970)"},{"key":"973_CR145","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1016\/j.disc.2008.01.002","volume":"309","author":"A. Nakamoto","year":"2009","unstructured":"Nakamoto A., Oda Y., Ota K.: 3-trees with few vertices of degree 3 in circuit graphs. Discrete Math. 309, 666\u2013672 (2009)","journal-title":"Discrete Math."},{"key":"973_CR146","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"C.St.J.A. Nash-Williams","year":"1961","unstructured":"Nash-Williams C.St.J.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36, 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"key":"973_CR147","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01375473","volume":"11","author":"V. Neumann-Lara","year":"1991","unstructured":"Neumann-Lara V., Rivera-Campo E.: Spanning trees with bounded degrees. Combinatorica 11, 55\u201361 (1991)","journal-title":"Combinatorica"},{"key":"973_CR148","unstructured":"Ohnishi, Y., Ota, K.: Connected factors with bounded total excess (2010, preprint)"},{"key":"973_CR149","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2307\/2308928","volume":"67","author":"O. Ore","year":"1960","unstructured":"Ore O.: Note on Hamilton circuits. Am. Math. Mon. 67, 55 (1960)","journal-title":"Am. Math. Mon."},{"key":"973_CR150","first-page":"21","volume":"42","author":"O. Ore","year":"1963","unstructured":"Ore O.: Hamilton connected graphs. J. Math. Pures Appl. 42, 21\u201327 (1963)","journal-title":"J. Math. Pures Appl."},{"key":"973_CR151","doi-asserted-by":"crossref","unstructured":"Ota, K., Ozeki, K.: Spanning trees in 3-connected K 3,t -minor-free graphs (2010, submitted)","DOI":"10.1016\/j.endm.2009.07.024"},{"key":"973_CR152","unstructured":"Ozeki, K.: Toughness condition for a spanning k-tree with bounded total excess (2010, submitted)"},{"key":"973_CR153","unstructured":"Ozeki, K.: Spanning trees in 3-connected graphs on surfaces (2010, preprint)"},{"key":"973_CR154","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s00373-010-0933-x","volume":"26","author":"K. Ozeki","year":"2010","unstructured":"Ozeki K., Yamashita T.: A spanning tree with high degree vertices. Graphs Combin. 26, 591\u2013596 (2010)","journal-title":"Graphs Combin."},{"key":"973_CR155","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0012-365X(00)00066-2","volume":"230","author":"E.M. Palmer","year":"2001","unstructured":"Palmer E.M.: On the spanning tree packing number of a graph: a survey. Discrete Math. 230, 13\u201321 (2001)","journal-title":"Discrete Math."},{"key":"973_CR156","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0012-365X(97)00034-4","volume":"179","author":"L. Petingi","year":"1998","unstructured":"Petingi L., Boesch F., SuLel C.: On the characterization of graphs with maximum number of spanning trees. Discrete Math. 179, 155\u2013166 (1998)","journal-title":"Discrete Math."},{"key":"973_CR157","first-page":"43","volume":"145","author":"L. Petingi","year":"2000","unstructured":"Petingi L., Rodriguez J.: Bounds on the maximum number of edge-disjoint Steiner trees of a graph. Congr. Numer. 145, 43\u201352 (2000)","journal-title":"Congr. Numer."},{"key":"973_CR158","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/S0012-365X(01)00095-4","volume":"244","author":"L. Petingi","year":"2002","unstructured":"Petingi L., Rodriguez J.: A new technique for the characterization of graphs with a maximum number of spanning trees. Discrete Math. 244, 351\u2013373 (2002)","journal-title":"Discrete Math."},{"key":"973_CR159","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1002\/net.20298","volume":"54","author":"L. Petingi","year":"2009","unstructured":"Petingi L., Talanfha M.: Packing the Steiner trees of a graph. Networks 54, 90\u201394 (2009)","journal-title":"Networks"},{"key":"973_CR160","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.3190080102","volume":"8","author":"J. Plesnik","year":"1984","unstructured":"Plesnik J.: On the sum of all distances in a graph or digraph. J. Graph Theory 8, 1\u201321 (1984)","journal-title":"J. Graph Theory"},{"key":"973_CR161","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1016\/j.disc.2005.11.059","volume":"307","author":"M.D. Plummer","year":"2007","unstructured":"Plummer M.D.: Graph factors and factorization: 1985\u20132003: a survey. Discrete Math. 307, 791\u2013821 (2007)","journal-title":"Discrete Math."},{"key":"973_CR162","first-page":"142","volume":"27","author":"H. Pr\u00fcfer","year":"1918","unstructured":"Pr\u00fcfer H.: Neuer Beweis eines Satzes \u00fcber Permutationen. Arch. Math. Phys. 27, 142\u2013144 (1918)","journal-title":"Arch. Math. Phys."},{"key":"973_CR163","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.ipl.2004.12.016","volume":"94","author":"M.S. Rahman","year":"2005","unstructured":"Rahman M.S., Kaykobad M.: Complexities of some interesting problems on spanning trees. Inform. Process. Lett. 94, 93\u201397 (2005)","journal-title":"Inform. Process. Lett."},{"key":"973_CR164","first-page":"19","volume":"90","author":"E. Rivera-Campo","year":"1992","unstructured":"Rivera-Campo E.: An Ore-type condition for the existence of spanning trees with bounded degrees. Congr. Numer. 90, 19\u201332 (1992)","journal-title":"Congr. Numer."},{"key":"973_CR165","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF03352993","volume":"13","author":"E. Rivera-Campo","year":"1997","unstructured":"Rivera-Campo E.: A note on matchings and spanning trees with bounded degrees. Graphs Combin. 13, 159\u2013165 (1997)","journal-title":"Graphs Combin."},{"key":"973_CR166","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/978-3-540-74456-6_10","volume":"4708","author":"G. Salamon","year":"2007","unstructured":"Salamon G.: Approximation algorithms for the maximum internal spanning tree problem. Lect. Notes Comput. Sci. 4708, 90\u2013102 (2007)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR167","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","volume":"105","author":"G. Salamon","year":"2008","unstructured":"Salamon G., Wiener G.: On finding spanning trees with few leaves. Inform. Process. Lett. 105, 164\u2013169 (2008)","journal-title":"Inform. Process. Lett."},{"key":"973_CR168","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1002\/1097-0118(200102)36:2<67::AID-JGT2>3.0.CO;2-C","volume":"36","author":"D.P. Sanders","year":"2001","unstructured":"Sanders D.P., Zhao Y.: On spanning trees and walks of low maximum degree. J. Graph Theory 36, 67\u201374 (2001)","journal-title":"J. Graph Theory"},{"key":"973_CR169","unstructured":"Seymour, P.D.: Sums of Circuits, Graph Theory and Relation Topics, pp. 341\u2013355. Academic Press, New York (1979)"},{"key":"973_CR170","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1109\/TCT.1968.1082765","volume":"15","author":"H. Shank","year":"1968","unstructured":"Shank H.: A note on hamilton circuits in tree graphs. IEEE Trans. Circuit Theory 15, 86 (1968)","journal-title":"IEEE Trans. Circuit Theory"},{"key":"973_CR171","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/3-540-68530-8_37","volume":"1461","author":"R. Solis-Oba","year":"1998","unstructured":"Solis-Oba R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Lect. Notes Comput. Sci. 1461, 441\u2013452 (1998)","journal-title":"Lect. Notes Comput. Sci."},{"key":"973_CR172","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/s00373-008-0804-x","volume":"24","author":"J. Szab\u00f3","year":"2008","unstructured":"Szab\u00f3 J.: Packing trees with constraints on the leaf degree. Graphs Combin. 24, 485\u2013494 (2008)","journal-title":"Graphs Combin."},{"key":"973_CR173","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1017\/S0004972700042660","volume":"8","author":"G. Szekeres","year":"1973","unstructured":"Szekeres G.: Polyhedral decomposition of cubic graphs. Bull. Austral. Math. Soc. 8, 367\u2013387 (1973)","journal-title":"Bull. Austral. Math. Soc."},{"key":"973_CR174","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1006\/jctb.1994.1005","volume":"60","author":"C. Thomassen","year":"1994","unstructured":"Thomassen C.: Trees in triangulations. J. Combin. Theory Ser. B 60, 56\u201362 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"973_CR175","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s00493-009-2349-x","volume":"29","author":"M. Tsugaki","year":"2009","unstructured":"Tsugaki M.: A note on a spanning 3-tree. Combinatorica 29, 127\u2013129 (2009)","journal-title":"Combinatorica"},{"key":"973_CR176","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s00373-007-0751-y","volume":"23","author":"M. Tsugaki","year":"2007","unstructured":"Tsugaki M., Yamashita T.: Spanning trees with few leaves. Graphs Combin. 23, 585\u2013598 (2007)","journal-title":"Graphs Combin."},{"key":"973_CR177","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"36","author":"W.T. Tutte","year":"1961","unstructured":"Tutte W.T.: On the problem of decomposing a graph into n connected factors. J. Lond. Math. Soc. 36, 221\u2013230 (1961)","journal-title":"J. Lond. Math. Soc."},{"key":"973_CR178","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"1996","unstructured":"West D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (1996)","edition":"2"},{"key":"973_CR179","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1002\/jgt.3190110309","volume":"11","author":"R.W. Whitty","year":"1987","unstructured":"Whitty R.W.: Vertex-disjoint paths and edge-disjoint branchings in directed graphs. J. Graph Theory 11, 349\u2013358 (1987)","journal-title":"J. Graph Theory"},{"key":"973_CR180","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02995957","volume":"43","author":"S. Win","year":"1975","unstructured":"Win S.: Existenz von Ger\u00fcsten mit vorgeschriebenem Maximalgrad in Graphen (German). Abh. Math. Sem. Univ. Hamburg 43, 263\u2013267 (1975)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"973_CR181","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF03322958","volume":"2","author":"S. Win","year":"1979","unstructured":"Win S.: On a conjecture of Las Vergnas concerning certain spanning trees in graphs. Result. Math. 2, 215\u2013224 (1979)","journal-title":"Result. Math."},{"key":"973_CR182","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF01788671","volume":"5","author":"S. Win","year":"1989","unstructured":"Win S.: On a connection between the existence of k-trees and the toughness of a graph. Graphs Combin. 5, 201\u2013205 (1989)","journal-title":"Graphs Combin."},{"key":"973_CR183","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1137\/0601008","volume":"1","author":"R. Wong","year":"1980","unstructured":"Wong R.: Worst-case analysis of network design problem heuristics. SIAM J. Algebraic Discrete Math. 1, 51\u201363 (1980)","journal-title":"SIAM J. Algebraic Discrete Math."},{"key":"973_CR184","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0166-218X(00)00185-2","volume":"105","author":"B.Y. Wu","year":"2000","unstructured":"Wu B.Y., Chao K.M., Tang C.Y.: Approximation algorithms for the shortest total path length spanning tree problem. Discrete Appl. Math. 105, 273\u2013289 (2000)","journal-title":"Discrete Appl. Math."},{"key":"973_CR185","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1137\/S009753979732253X","volume":"29","author":"B.Y. Wu","year":"2000","unstructured":"Wu B.Y., Lancia G., Bafna V., Chao K.M., Ravi R., Tang C.Y.: A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput. 29, 761\u2013778 (2000)","journal-title":"SIAM J. Comput."},{"key":"973_CR186","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/S0012-365X(96)00092-1","volume":"169","author":"X.R. Yong","year":"1997","unstructured":"Yong X.R., Acenjian T.: The numbers of spanning trees of the cycle C 3 N and the quadruple cycle C 4 N . Discrete Math. 169, 293\u2013298 (1997)","journal-title":"Discrete Math."},{"key":"973_CR187","first-page":"225","volume":"60","author":"K. Yoshimoto","year":"2001","unstructured":"Yoshimoto K.: The connectivities of trunk graphs of 2-connected graphs. Ars Combin. 60, 225\u2013237 (2001)","journal-title":"Ars Combin."},{"key":"973_CR188","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1090\/S0002-9947-97-01830-8","volume":"349","author":"X. Yu","year":"1997","unstructured":"Yu X.: Disjoint paths, planarizing cycles, and spanning walks. Trans. Am. Math. Soc. 349, 1333\u20131358 (1997)","journal-title":"Trans. Am. Math. Soc."},{"key":"973_CR189","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1002\/jgt.3190130205","volume":"13","author":"A. Zehavi","year":"1989","unstructured":"Zehavi A., Itai A.: Three tree-paths. J. Graph Theory 13, 175\u2013188 (1989)","journal-title":"J. Graph Theory"},{"key":"973_CR190","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0012-365X(91)90401-M","volume":"89","author":"S.M. Zhan","year":"1991","unstructured":"Zhan S.M.: On Hamiltonian line graphs and connectivity. Discrete Math. 89, 89\u201395 (1991)","journal-title":"Discrete Math."},{"key":"973_CR191","first-page":"1","volume":"3","author":"F.J. Zhang","year":"1986","unstructured":"Zhang F.J., Chen Z.: Connectivity of (adjacency) tree graphs. J. Xinjiang Univ. Nat. Sci. 3, 1\u20135 (1986)","journal-title":"J. Xinjiang Univ. Nat. Sci."},{"key":"973_CR192","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0012-365X(99)00414-8","volume":"223","author":"Y. Zhang","year":"2000","unstructured":"Zhang Y., Yong X., Golin M.J.: The number of spanning trees in circulant graphs. Discrete Math. 223, 337\u2013350 (2000)","journal-title":"Discrete Math."},{"key":"973_CR193","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1002\/(SICI)1097-0118(199806)28:2<87::AID-JGT2>3.0.CO;2-A","volume":"28","author":"L. Zhenhong","year":"1998","unstructured":"Zhenhong L., Baoguang X.: On low bound of degree sequences of spanning trees in k-edge- connected graphs. J. Graph Theory 28, 87\u201395 (1998)","journal-title":"J. Graph Theory"},{"key":"973_CR194","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/S0012-365X(00)00453-2","volume":"236","author":"I.A. Zio\u0142o","year":"2001","unstructured":"Zio\u0142o I.A.: Subforests of bipartite figraphs\u2014the minimum degree condition. Discrete Math. 236, 351\u2013365 (2001)","journal-title":"Discrete Math."},{"key":"973_CR195","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0166-218X(99)00137-7","volume":"99","author":"I.A. Zio\u0142o","year":"2000","unstructured":"Zio\u0142o I.A.: Subtrees of bipartite figraphs\u2014the minimum degree condition. Discrete Appl. Math. 99, 251\u2013259 (2000)","journal-title":"Discrete Appl. Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-010-0973-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-010-0973-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-010-0973-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T02:05:15Z","timestamp":1591841115000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-010-0973-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,1]]},"references-count":195,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["973"],"URL":"https:\/\/doi.org\/10.1007\/s00373-010-0973-2","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,1]]}}}