Article

Lower bounds on the leaf number in graphs with forbidden subgraphs

Published in: Quaestiones Mathematicae
Volume 40 , issue 1 , 2017 , pages: 139–149

DOI: 10.2989/16073606.2017.1282892

Author(s): P. Mafuta Department of Mathematics, Zimbabwe , S. Mukwembi Department of Mathematics, Zimbabwe , S. Munyira Department of Mathematics, Zimbabwe , B.G. Rodrigues School of Mathematics, Statistics and Computer Science, South Africa

Keywords: 05C05 , 05C05

Download full text Get new issue alerts

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 C₄−free graphs.

« Dominated operators, absolutely summing operators and the strict topology

Global stability for the continuous and discrete SIS-diffusion epidemiological models »