TY  - JOUR
ID  - Cai2017
LB  - Cai2017
AU  - Cai, Junqing
AU  - Flandrin, Evelyne
AU  - Li, Hao
AU  - Sun, Qiang
TI  - Spanning trees with a bounded number of leaves
ST  - Spanning trees with a bounded number of leaves
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2017
VL  - 37
IS  - 4
SP  - 501
EP  - 508
DO  - http://dx.doi.org/10.7494/OpMath.2017.37.4.501
UR  - http://dx.doi.org/10.7494/OpMath.2017.37.4.501
AB  - 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.
KW  - spanning tree
KW  - implicit degree
KW  - leaves
SN  - 1232-9274
ER  -