Browsing by Subject "implicit degree"

Now showing 1 - 1 of 1

Access status: Open Access ,
Spanning trees with a bounded number of leaves
(Wydawnictwa AGH, 2017) Cai, Junqing; Flandrin, Evelyne; Li, Hao; Sun, Qiang
In 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph $G$ with $n\geq 3$ vertices, if $d(u)+d(v)\geq n-k+1$ for all non-adjacent vertices u and v of $G(k\geq 1)$, then $G$ has a spanning tree with at most $k$ leaves. In this paper, we generalize this result by using implicit degree sum condition of $t$($2\leq t\leq k$) independent vertices and we prove what follows: Let $G$ be a connected graph on $n\geq 3$ vertices and $k\geq 2$ be an integer. If the implicit degree sum of any $t$ independent vertices is at least $\frac{t(n-k)}{2}+1$ for ($k\geq t\geq 2$), then $G$ has a spanning tree with at most $k$ leaves.