|
Zapiski Nauchnykh Seminarov POMI, 2016, Volume 450, Pages 62–73
(Mi znsl6337)
|
|
|
|
Lower bounds on the number of leaves in spanning trees
D. V. Karpovab a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
b St. Petersburg State University, St. Petersburg, Russia
Abstract:
Let $G$ be a connected graph on $n\ge2$ vertices with girth at least $g$. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge1$. Denote by $u(G)$ the maximal number of leaves in a spanning tree of $G$. We prove, that $u(G)\ge\alpha_{g,k}(v(G)-k-2)+2$, where $\alpha_{g,1}=\frac{[\frac{g+1}2]}{4[\frac{g+1}2]+1}$ and $\alpha_{g,k}=\frac1{2k+2}$ for $k\ge2$. We present infinite series of examples showing that all these bounds are tight.
Key words and phrases:
spanning tree, number of leaves.
Received: 11.10.2016
Citation:
D. V. Karpov, “Lower bounds on the number of leaves in spanning trees”, Combinatorics and graph theory. Part VIII, Zap. Nauchn. Sem. POMI, 450, POMI, St. Petersburg, 2016, 62–73; J. Math. Sci. (N. Y.), 232:1 (2018), 36–43
Linking options:
https://www.mathnet.ru/eng/znsl6337 https://www.mathnet.ru/eng/znsl/v450/p62
|
Statistics & downloads: |
Abstract page: | 190 | Full-text PDF : | 51 | References: | 44 |
|