On minimum leaf spanning trees and a criticality notion. (English) Zbl 1440.05062

Summary: The minimum leaf number of a connected non-Hamiltonian graph \(G\) is the number of leaves of a spanning tree of \(G\) with the fewest leaves among all spanning trees of \(G\). Based on this quantity, Wiener introduced leaf-stable and leaf-critical graphs, concepts which generalise hypotraceability and hypohamiltonicity. In this article, we present new methods to construct leaf-stable and leaf-critical graphs and study their properties. Furthermore, we improve several bounds related to these families of graphs. These extend previous results of J. A. Horton [“A hypotraceable graph”, Res. Rep. CoRR 73–4 (1973)], C. Thomassen [Discrete Math. 14, 377–389 (1976; Zbl 0322.05130)], and G. Wiener [J. Graph Theory 84, No. 4, 443–459 (2017; Zbl 1359.05072)].


05C05 Trees
Full Text: DOI


[1] Gargano, L.; Hammar, M.; Hell, P.; Stacho, L.; Vaccaro, U., Spanning spiders and light-splitting switches, Discrete Math., 285, 83-95 (2004) · Zbl 1044.05048
[2] Goedgebeur, J.; Zamfirescu, C. T., Improved bounds for hypohamiltonian graphs, Ars Math. Contemp., 13, 235-257 (2017) · Zbl 1380.05034
[3] Goedgebeur, J.; Zamfirescu, C. T., On almost hypohamiltonian graphs, Discrete Math. Theoret. Comput. Sci., 21, #5 (2019) · Zbl 1417.05114
[4] Holton, D. A.; Sheehan. The Petersen Graph, J., Hypohamiltonian Graphs (1993), Cambridge University Press: Cambridge University Press New York, (Chapter 7)
[5] Horton, J. D., A Hypotraceable GraphResearch Report CORR 73-4 (1973), Dept. Combin. and Optim. Univ. Waterloo
[6] Jooyandeh, M.; McKay, B. D.; Östergård, P. R.J.; Pettersson, V. H.; Zamfirescu, C. T., Planar hypohamiltonian graphs on 40 vertices, J. Graph Theory, 84, 121-133 (2017) · Zbl 1356.05029
[7] Lu, H.-I.; Ravi, R., The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree (DRAFT)CS-96-05 (1996), Department of Computer Science, Brown University, Providence: Department of Computer Science, Brown University, Providence Rhode Island
[8] Neyt, A., Platypus graphs: Structure and generation (2017), Ghent University, (M.Sc. thesis)
[9] Salamon, G.; Wiener, G., On finding spanning trees with few leaves, Inform. Process. Lett., 105, 164-169 (2008) · Zbl 1184.68647
[10] Thomassen, C., Hypohamiltonian and hypotraceable graphs, Discrete Math., 9, 91-96 (1974) · Zbl 0278.05110
[11] Thomassen, C., Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math., 14, 377-389 (1976) · Zbl 0322.05130
[12] Thomassen, C., (Hypohamiltonian Graphs and Digraphs. Theory and Applications of Graphs. Hypohamiltonian Graphs and Digraphs. Theory and Applications of Graphs, Lecture Notes in Mathematics, vol. 642 (1978), Springer: Springer Berlin), 557-571 · Zbl 0371.05015
[13] Wiener, G., Leaf-critical and leaf-stable graphs, J. Graph Theory, 84, 443-459 (2017) · Zbl 1359.05072
[14] Wiener, G., New constructions of hypohamiltonian and hypotraceable graphs, J. Graph Theory, 87, 526-535 (2018) · Zbl 1386.05102
[15] Zamfirescu, T., On longest paths and circuits in graphs, Math. Scand., 38, 211-239 (1976) · Zbl 0337.05127
[16] Zamfirescu, C. T., On non-hamiltonian graphs for which every vertex-deleted subgraph is traceable, J. Graph Theory, 86, 223-243 (2017) · Zbl 1370.05115
[17] Zamfirescu, C. T., Cubic vertices in planar hypohamiltonian graphs, J. Graph Theory, 90, 189-207 (2019) · Zbl 1466.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.