Lower bounds on the leaf number in graphs with forbidden subgraphs

Abstract

Let G be a simple, connected graph. The leaf number, L(G) of G, is dened as the maximum number of leaf vertices contained in a spanning tree of G. Assume that G is a triangle-free graph with minimum degree δ, order n and leaf number L(G). We show that L(G) ≥ ^{δ - 1} /_{δ + 3}n + c_δ for δ= 4 and δ= 5, where c_δ is a constant that depends on δ only. Similar bounds are shown to hold for triangle-free and C₄-free graphs.

Mathematics Subject Classication (2010): 05C05.

Key words: Leaf number, minimum degree, order, triangle-free graphs.