zbMATH — the first resource for mathematics

Spanning trees in graphs of minimum degree 4 or 5. (English) Zbl 0776.05031
Summary: For a connected simple graph \(G\) let \(L(G)\) denote the maximum number of leaves in any spanning tree of \(G\). Lineal conjectured that if \(G\) has \(N\) vertices and minimum degree \(k\), then \(L(G)\geq((k-2)/(k+1))N+c_ k\), where \(c_ k\) depends on \(k\). We prove that if \(k=4\), \(L(G)\geq{2\over 5}N+{8\over 5}\); if \(k=5\), \(L(G)\geq{1\over 2}N+2\). We give examples showing that these bounds are sharp.

05C05 Trees
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Griggs, J.R.; Kleitman, D.J.; Shastri, A., Spanning trees with many leaves in cubic graphs, J. graph theory, 13, 669-695, (1989) · Zbl 0693.05023
[2] D.J. Kleitman and D.B. West, Spanning trees with many leaves, SIAM J. Discrete Math., to appear. · Zbl 0734.05041
[3] Kleitman, D.J.; West, D.B., Spanning trees with many leaves, SIAM discrete math. conf. San Francisco, (1988), lecture at · Zbl 0734.05041
[4] Lemke, P., The maximum leaf spanning tree problem for cubic graphs is NP-complete, Institute for mathematics and its application, (1988), preprint
[5] N. Linial, personal communication, 1988.
[6] Storer, J.A., Constructing full spanning trees for cubic graphs, Inform. process. lett., 13, 8-11, (1981) · 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.