zbMATH — the first resource for mathematics

Minimum degree, leaf number and traceability. (English) Zbl 1289.05261
Summary: Let \(G\) be a finite connected graph with minimum degree \(\delta \). The leaf number \(L(G)\) of \(G\) is defined as the maximum number of leaf vertices contained in a spanning tree of \(G\). We prove that if \(\delta \geq \frac {1}{2}(L(G)+1)\), then \(G\) is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if \(\delta \geq \smash {\frac {1}{2}}(L(G)+1)\), then \(G\) contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [E. DeLaViña and B. Waller, Electron. J. Comb. 15, No. 1, R33, 16 p. (2008; Zbl 1181.05052)]. For \(G\) claw-free, we show that if \(\delta \geq \frac {1}{2}(L(G)+1)\), then \(G\) is Hamiltonian. This again confirms, and even improves, the conjecture of Graffiti.pc for this class of graphs.

05C45 Eulerian and Hamiltonian graphs
Zbl 1181.05052
Full Text: DOI Link
[1] R. Čada, E. Flandrin, H. Kang: A note on degree conditions for traceability in locally claw-free graphs. Math. Comput. Sci. 5 (2011), 21–25. · Zbl 1254.05085
[2] E. DeLaViña: Written on the Wall II (Conjectures of Graffiti.pc). http://cms.dt.uh.edu/faculty/delavinae/research/wowII/ .
[3] E. DeLaViña, B. Waller: Spanning trees with many leaves and average distance. Electron. J. Comb. 15 (2008), 16 p. · Zbl 1181.05052
[4] G. Ding, T. Johnson, P. Seymour: Spanning trees with many leaves. J. Graph Theory 37 (2001), 189–197. · Zbl 0986.05030
[5] D. Duffus, M. S. Jacobson, R. J. Gould: Forbidden subgraphs and the Hamiltonian theme. The Theory and Applications of Graphs. 4th int. Conf., Kalamazoo/Mich. 1980, Wiley, New York, 1981, pp. 297–316.
[6] L.M. Fernandes, L. Gouveia: Minimal spanning trees with a constraint on the number of leaves. Eur. J. Oper. Res. 104 (1998), 250–261. · Zbl 0957.90010
[7] S. Goodman, S. Hedetniemi: Sufficient conditions for a graph to be Hamiltonian. J. Comb. Theory, Ser. B 16 (1974), 175–180. · Zbl 0275.05126
[8] R. J. Gould, M. S. Jacobson: Forbidden subgraphs and Hamiltonian properties and graphs. Discrete Math. 42 (1982), 189–196. · Zbl 0495.05039
[9] J. R. Griggs, M. Wu: Spanning trees in graphs of minimum degree 4 or 5. Discrete Math. 104 (1992), 167–183. · Zbl 0776.05031
[10] D. J. Kleitman, D.B. West: Spanning trees with many leaves. SIAM J. Discrete Math. 4 (1991), 99–106. · Zbl 0734.05041
[11] H. Li: Hamiltonian cycles in 2-connected claw-free-graphs. J. Graph Theory 20 (1995), 447–457. · Zbl 0841.05062
[12] S. Mukwembi, S. Munyira: Radius, diameter and the leaf number. Quaest. Math. (Submitted).
[13] S. Ren: A sufficient condition for graphs with large neighborhood unions to be traceable. Discrete Math. 161 (1996), 229–234. · Zbl 0869.05041
[14] J.A. Storer: Constructing full spanning trees for cubic graphs. Inf. Process Lett. 13(1981), 8–11. · Zbl 0482.05031
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.