Maximum number of subtrees in cacti and block graphs

For a graph G, we denote by N(G) the number of non-empty subtrees of G. As a topological index based on counting, N(G) has some correlations to other well studied topological indices, including the Wiener index W(G). In this paper we characterize the extremal graphs with the maximum number of subtrees among all cacti of order n with k cycles. Similarly, the extremal graphs with the maximum number of subtrees among all block graphs of order n with k blocks are also determined and shown to have the minimum Wiener index within the same collection of graphs. Analogous results are also obtained for the number of connected subgraphs C(G). Finally, a general question is posed concerning the relation between the number of subtrees and the Wiener index of graphs.