A bound on the number of leaves in a spanning tree of a connected graph of minimal degree 6
E. N. Simarova St. Petersburg State University, St. Petersburg, Russia
Abstract:
It is proved, that a connected graph of minimal degree 6 has a spanning tree, such that at least
$\frac{11}{21}$ of its vertices are leaves.
Key words and phrases:
distance graph, independence number, Turán type bounds.
UDC:
519.172.1 Received: 27.11.2017
© , 2025
Fulltext:
PDF file (226 kB)
