科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let G be a finite connected graph with minimum degree delta. The leaf number L(G) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G. We prove that if delta a (c) 3/4 1/2 (L(G) + 1), then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if delta a (c) 3/4 1/2 (L(G) + 1), then G contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVia and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin. 15 (2008), 1-16].
- 出版日期2013-6
