A Note on Leaf-constrained Spanning Trees in a Graph

Abstract

An independent set \(S\) of a connected graph \(G\) is called a \emph{frame} if \(G – S\) is connected. If \(|S| = k\), then \(S\) is called a \emph{k-frame}. We prove the following theorem.
Let \(k \geq 2\) be an integer, \(G\) be a connected graph with \(V(G) = \{v_1, v_2, \ldots, v_n\}\), and \(\deg_G(u)\) denote the degree of a vertex \(u\). Suppose that for every \(3\)-frame \(S = \{v_a, v_b, v_c\}\) such that \(1 \leq a \leq b \leq c \leq n\), \(\deg_G(v_c) \leq a\), \(\deg_G(v_b) \leq b-1\), and \(\deg_G(v_c) \leq c – 2\), it holds that\[\deg_G(v_a) + \deg_G(v_b) + \deg_G(v_c) – |N(v_a) \cap N(v_b) \cap N(v_c)| \geq |G| – k + 1.\] Then \(G\) has a spanning tree with at most \(k\)-leaves. Moreover, the condition is sharp.
This theorem is a generalization of the results of E. Flandrin, H.A. Jung, and H. Li (Discrete Math. \(90 (1991), 41-52)\) and of A. Kyaw (Australasian Journal of Combinatorics. \(37 (2007), 3-10)\) for traceability.