The number of subtrees in graphs with given number of cut edges

The number of non-empty subtrees of a connected graph G, denoted by N(G), has been an interesting topic of research for many years. Considered as a counting based topological index, it appears to have correlations with many other well studied graph indices. Many results on various extremal trees with respect to the number of subtrees have been established over the years. But relatively few are available on more general graphs. In this paper we consider the maximum and minimum values of N(G) among connected graphs of a given order n and k >= 0 cut edges. Sharp upper bounds are presented with the corresponding extremal structures for each k >= 0, and sharp lower bounds are presented with the corresponding extremal structures for 0 <= k < n-1/2. (C) 2021 Elsevier B.V. All rights reserved.