RADIUS, LEAF NUMBER, CONNECTED DOMINATION NUMBER AND MINIMUM DEGREE

Let G be a simple, connected graph with minimum degree delta, radius r and leaf number L(G). We prove that L(G)>={2/3 (r - 1/2) (delta - 2) + 2 if r equivalent to 2 modulo 3, 2/3 r(delta - 2) + 2 if r equivalent to 0 modulo 3, 2/3 (r - 1) (delta - 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 equivalent to 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.