×

zbMATH — the first resource for mathematics

Leaf-critical and leaf-stable graphs. (English) Zbl 1359.05072
Summary: The minimum leaf number \(\mathrm{ml}(G)\) of a connected graph \(G\) is defined as the minimum number of leaves of the spanning trees of \(G\) if \(G\) is not Hamiltonian and 1 if \(G\) is Hamiltonian. We study nonhamiltonian graphs with the property \(l:=\mathrm{ml}(G-v)=\mathrm{ml}(G)-1\) for each \(v\in V(G)\) or \(l:=\mathrm{ml}(G-v)=\mathrm{ml}(G)\) for each \(v\in V(G)\). These graphs will be called \((l+1)\)-leaf-critical and \(l\)-leaf-stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3-leaf-critical graphs (that turn out to be the so-called hypotraceable graphs) was an open problem until 1975 [C. Thomassen, Discrete Math. 14, 377–389 (1976; Zbl 0322.05130); T. Zamfirescu, Math. Scand. 38, 211–239 (1976; Zbl 0337.05127)]. We show that \(l\)-leaf-stable and \(l\)-leaf-critical graphs exist for every integer \(l\geq2\), moreover for \(n\) sufficiently large, planar \(l\)-leaf-stable and \(l\)-leaf-critical graphs exist on \(n\) vertices. We also characterize 2-fragments of leaf-critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf-critical graphs constructed, we settle an open problem of L. Gargano et al. [Discrete Math. 285, No. 1–3, 83–95 (2004; Zbl 1044.05048)] concerning spanning spiders. We also explore connections with a family of graphs introduced by B. Grünbaum [J. Comb. Theory, Ser. A 17, 31–38 (1974; Zbl 0259.05120)] in correspondence with the problem of finding graphs without concurrent longest paths.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldred, Small hypohamiltonian graphs, J Combin Math Combin Comput 23 pp 143– (1997) · Zbl 0880.05061
[2] Araya, On cubic planar hypohamiltonian and hypotraceable graphs, Electron J Combin 18 (2011) · Zbl 1217.05065
[3] Binkele-Raible, Exact and parameterized algorithms for max internal spanning tree, Algorithmica 65 pp 95– (2009) · Zbl 1259.05159 · doi:10.1007/s00453-011-9575-5
[4] Chvátal, Flip-flops in hypohamiltonian graphs, Can Math Bull 16 pp 33– (1973) · Zbl 0253.05142 · doi:10.4153/CMB-1973-008-9
[5] Doyen, New families of hypohamiltonian graphs, Discrete Math 13 pp 225– (1975) · Zbl 0312.05114 · doi:10.1016/0012-365X(75)90020-5
[6] Gallai, Theory of Graphs pp 115– (1968)
[7] Gargano, Spanning spiders and light-splitting switches, Discrete Math 285 pp 83– (2004) · Zbl 1044.05048 · doi:10.1016/j.disc.2004.04.005
[8] Grünbaum, Vertices missed by longest paths or circuits, J Comb Theory Ser A 17 pp 31– (1974) · Zbl 0259.05120 · doi:10.1016/0097-3165(74)90025-9
[9] Herz, Solution du probléme No. 29, Rev Fr Rech Operat 8 pp 214– (1964)
[10] Holton, The Petersen Graph (1993) · Zbl 0781.05001 · doi:10.1017/CBO9780511662058
[11] Hsu, Graph Theory and Interconnection Networks (2008)
[12] M. Jooyandeh B. D. McKay P. R. J. Östergård V. H. Pettersson C. T. Zamfirescu Planar hypohamiltonian graphs on 40 vertices 2013
[13] Kapoor, On detours in graphs, Can Math Bull 11 pp 195– (1968) · Zbl 0167.22002 · doi:10.4153/CMB-1968-022-8
[14] Salamon, Degree-Based Spanning Tree Optimization (2010)
[15] Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math 9 pp 91– (1974) · Zbl 0278.05110 · doi:10.1016/0012-365X(74)90074-0
[16] Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math 14 pp 377– (1976) · Zbl 0322.05130 · doi:10.1016/0012-365X(76)90071-6
[17] Thomassen, Theory and Application of Graphs, Lecture Notes in Mathematics 642 pp 557– (1978) · Zbl 0371.05015 · doi:10.1007/BFb0070410
[18] Walther, Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen, J Comb Theory 6 pp 1– (1969) · Zbl 0184.27504 · doi:10.1016/S0021-9800(69)80098-0
[19] Wiener, On planar hypohamiltonian graphs, J Graph Theory 67 pp 55– (2011) · Zbl 1223.05168 · doi:10.1002/jgt.20513
[20] Zamfirescu, On longest paths and circuits in graphs, Math Scand 38 pp 211– (1976) · Zbl 0337.05127 · doi:10.7146/math.scand.a-11630
[21] Zamfirescu, A two-connected planar graph without concurrent longest paths, J Comb Theory Ser B 13 pp 116– (1978) · Zbl 0243.05110 · doi:10.1016/0095-8956(72)90048-2
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.