Lower bounds on the leaf number in graphs with forbidden subgraphs. Issue 1 (2nd January 2017)

• Record Type: Journal Article
• Authors: Mafuta, P.; Mukwembi, S.; Munyira, S.; Rodrigues, B.G.
• Is Part Of: Quaestiones mathematicae. Volume 40:Issue 1(2017)
• Page Start: 139
• Page End: 149
• Publication Date: 2017-01-02
• Subjects: 05C05; Leaf number -- minimum degree -- order -- triangle-free graphs; Mathematics -- Periodicals; 510.5
• DOI: 10.2989/16073606.2017.1282892
• Languages: English
• ISSNs: 1607-3606

Abstract

Abstract: Let G be a simple, connected graph. The leaf number, L ( G ) of G, is defined 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 for δ = 4 and δ = 5, where c δ is a constant that depends on δ only. Similar bounds are shown to hold for triangle − free and C4 −free graphs.