2018/06/12 by Jan Goedgebeur, Goedgebeur, Jan, Kenta Ozeki +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1806.04451
17 pages
arxiv created 2018/06/12 · arxiv updated 2018/06/13
The minimum leaf number \hboxml (G) of a connected graph G is defined as the minimum number of leaves of the spanning trees of G. We present new results concerning the minimum leaf number of cubic graphs: we show that if G is a connected cubic graph of order n, then ml(G) ≤ \fracn6 + \frac13, improving on the best known result in [Inf. Process. Lett. 105 (2008) 164-169] and proving the conjecture in [Electron. J. Graph Theory and Applications 5 (2017) 207-211]. We further prove that if G is also 2-connected, then ml(G) ≤ (n)/(6.53), improving on the best known bound in [Math. Program., Ser. A 144 (2014) 227-245]. We also present new conjectures concerning the minimum leaf number of several types of cubic graphs and examples showing that the bounds of the conjectures are best possible.