On the minimum number of components in a cotree of a graph (Q2702779)

The decay number \(\zeta (G)\) of a simple graph \(G\) is the smallest number of components of the cotrees of \(G\), i.e., \(\zeta (G) =\min \{c (G-E(T))\): \(T\) is a spanning tree of \(G\}\), where \(c(G)\) denotes the number of components of the graph \(G\). NEWLINENEWLINENEWLINEA leaf of graph \(G\) is any 2-edge connected subgraph of \(G\), trivial or not, maximal with respect to inclusion. The main result of the paper is the following: Let \(G\) be a connected graph and \(l(G)\) denote the number of leaves of \(G\). Then \(\zeta (G) = \max \{l(G-A) - |A|: A\subseteq E(G)\}\). An application to graphs of diameter 2 is also presented.