Radius, leaf number, connected domination number and minimum degree

Abstract

Let G be a simple, connected graph with minimum degree δ, radius r

and leaf number L(G). We prove that

             L(G)≥   {⅔ (r-½) (δ-2)+2 if r Ξ 2 modulo 3,

                        ⅔ r (δ-2)+2 if r Ξ 0 modulo 3,

                        ⅔ (r-1) (δ-2)+2 otherwise.}

We give similar bounds for triangle-free graphs. Infinite families of graphs are constructed to show that all the bounds here are sharp, except the one for r Ξ 1 modulo 3 in the above piecewise inequality. The results bring to literature new lower bounds on the leaf number and new upper bounds on the radius and connected domination number of a graph. Further, the techniques applied in this paper can be used to improve known asymptotically sharp bounds on the radius and diameter to sharp bounds. We consider simple graphs only.