On a conjecture by Griggs, Kleitman and Shastri

Abstract

Let $G$ be a simple, connected graph. The \textit{leaf number}, $L(G)$, is the maximum number of leaf vertices contained in a spanning tree of $G$. The cardinality of the smallest connected dominating set in $G$ is the \textit{connected domination number}, $\gamma_c(G)$. The \textit{girth} $g(G)$ is the length of a shortest cycle in a graph. If $G$ has girth $g(G)\ge 5$, minimum degree $\delta(G)\ge3$, order $n(G)$, leaf number $L(G)$ and connected domination number $\gamma_c(G)$, we prove that $L(G)\ge \dfrac{2}{5}n(G)+\dfrac{4}{5}$. That is, $\gamma_c(G)\le \dfrac{3}{5}n(G)-\dfrac{4}{5}$ and the bound is asymptotically sharp. This settles completely, a conjecture by Griggs, Kleitman and Shastri.