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 NameAffiliation
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
Download times: 1637
Abstract:
      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\}$.
Citation:
DOI:10.3770/j.issn:2095-2651.2016.04.007
View Full Text  View/Add Comment  Download reader