Degree Conditions for Spanning Brooms |
| |
Authors: | Guantao Chen Michael Ferrara Zhiquan Hu Michael Jacobson Huiqing Liu |
| |
Institution: | 1. DEPARTMENT OF MATHEMATICS AND STATISTICS, GEORGIA STATE UNIVERSITY, ATLANTA, GAContract grant sponsor: Research Supported in part by NSA grant number H98230‐12‐1‐0239. Research Supported in part by Simons Foundation grant number 206692. Research Supported in part by NSFC grant numbers: 11071096;2. 11271149;3. and 11371162. Research Supported in part by NSF grant number DGE‐0742434. Research Supported in part by NSFC grant number 10971114.;4. DEPARTMENT OF MATHEMATICAL AND STATISTICAL SCIENCES, UNIVERSITY OF COLORADO DENVER, DENVER, CO;5. FACULTY OF MATHEMATICS AND STATISTICS, CENTRAL CHINA NORMAL UNIVERSITY, WUHAN, CHINA;6. SCHOOL OF MATHEMATICS AND COMPUTER SCIENCE, HUBEI UNIVERSITY, WUHAN, CHINA |
| |
Abstract: | A broom is a tree obtained by subdividing one edge of the star an arbitrary number of times. In (E. Flandrin, T. Kaiser, R. Ku?el, H. Li and Z. Ryjá?ek, Neighborhood Unions and Extremal Spanning Trees, Discrete Math 308 (2008), 2343–2350) Flandrin et al. posed the problem of determining degree conditions that ensure a connected graph G contains a spanning tree that is a broom. In this article, we give one solution to this problem by demonstrating that if G is a connected graph of order with , then G contains a spanning broom. This result is best possible. |
| |
Keywords: | extremal spanning tree broom |
|
|