Spanning Trees with Few Leaves in Almost Claw-Free Graphs
Received:October 20, 2015  Revised:April 15, 2016
Key Word: spanning 3-ended tree   almost claw-free graph   insertible vertex, non-insertible vertex
Fund ProjectL:Supported by the National Natural Science Foundation of China, Tian Yuan Special Foundation (Grant No.11426125), by Educational Commission of Liaoning Province (Grant No.L2014239).
 Author Name Affiliation Xiaodong CHEN College of Science, Liaoning University of Technology, Liaoning 121001, P. R. China Mingchu LI School of Softsware, Dalian University of Technology, Liaoning 116024, P. R. China Meijin XU College of Science, Liaoning University of Technology, Liaoning 121001, P. R. China
Hits: 2147
A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if $G$ is a $k$-connected ($k\geq 2$) almost claw-free graph of order $n$ and $\sigma_{k+3}(G)\geq {n+k+2}$, then $G$ contains a spanning 3-ended tree, where $\sigma_k(G)=\min\{\sum_{v\in S}{\rm deg}(v):S$ is an independent set of $G$ with $|S|=k\}$.