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

Ozeki, Kenta; Wiener, Gábor; Zamfirescu, Carol T.

Discrete Math. 343, No. 7, Article ID 111884, 7 p. (2020).

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)].

MSC:

05C05

Trees

Keywords:

spanning tree; minimum leaf number; leaf-stable; leaf-critical

Citations:

Zbl 0322.05130; Zbl 1359.05072

Software:

GenHypohamiltonian

References:

[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) · Zbl 0781.05001
[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