Spanning trees with many leaves |
| |
Authors: | D V Karpov |
| |
Institution: | 1.St. Petersburg Department of the Steklov Mathematical Institute,St. Petersburg,Russia |
| |
Abstract: | Let a maximal chain of vertices of degree 2 in a graph G consist of k > 0 vertices. We prove that G has a spanning tree with more than
\fracv(G)2k + 4 \frac{{v(G)}}{{2k + 4}} leaves (where υ(G) is the number of vertices of the graph G). We present an infinite series of examples showing that the constant
\frac12k + 4 \frac{1}{{2k + 4}} cannot be enlarged. Bibliography: 7 titles. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |