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.

Keywords: Number of subtrees; Cactus graph; Block graph; 05C05; 05C30; 05C35

Throughout this paper we only consider undirected, finite and simple graphs. We denote by $C_n$ and $K_n$ the cycle and the complete graph on n vertices, respectively. Similarly, $P_n$ and $S_n$ are the path and the star on n vertices, respectively. Other undefined notations and terminologies can be found in [[5]].

The number of subtrees was first studied for trees in [[18]] in 2005. For any connected graph G, we denote by N(G) the number of non-empty subtrees. The properties of N(T) have been studied for various classes of trees [[1], [7], [11], [17], [19], [26]]. However, there are few results on N(G) for general graphs G. Recently, Andriantiana and Wang [[3]] considered extremal unicyclic graphs with respect to N. Furthermore, the present authors [[24]] characterized extremal graphs with respect to N among all connected graphs of order n with k cut edges. For a subtree T of aconnected graph G, we denote by N(T, G) the number of subtrees of G that contain T as an induced subgraph. In particular, if $V(T)=\{v\}$ or $V(T)=\{u,v\}$ , then N(T, G) can also be denoted by N(v, G) or N(uv, G), respectively. More generally, for any subgraph H of a graph G with $v\in V(H)$ , we denote by $N_G(v,H)$ the number of subtrees of H in G that contain v. Similarly, for a set $V=\{v_1,v_2,...,v_t\}\subseteq V(G)$ with $t\ge 2$ , $N(v_1,v_2,...,v_t;G)$ is the number of non-empty subtrees of G that contain the vertices $v_1,v_2,...,v_t$ .

As one of the most well-studied topological indices in chemical graph theory, the Wiener index [[21]] of a connected graph G is defined as

$$\begin{array}{c}\hfill W(G)=\sum _{\{u,v\}\subseteq V(G)}{d}_G(u,v)\end{array}$$

Graph

where $d_G(u,v)$ is the distance between two vertices u and v in G. For some recent results on the Wiener index of graphs, see [[4], [6], [9], [22], [25]].

An interesting "negative" correlation has been observed between the number of subtrees and the Wiener index of general graphs. It was shown that in some given collection of connected graphs, the extremal graphs minimizing (maximizing, resp.) the number of subtrees are often identical to the extremal graphs maximizing (minimizing, resp.) the Wiener index. Such collections of graphs include various classes of trees [[18], [23]] and unicyclic graphs [[3], [23]]. Some other results related to this correlation can be found in [[17], [19], [24]].

A block of a graph is a maximal 2-connected subgraph of this graph. A connected graph is a cactus if each block is an edge or a cycle. A connected graph is called block graph if each of its blocks is a clique. Some recent results on extremal problems concerning cacti can be found in [[15]]. A graph is a generalized complete graph [[20]] if it is obtained by the join of an isolated vertex with a disjoint union of one or more complete graphs. If G is a generalized complete graph with $u\in V(G)$ of degree $n-1$ such that $G-u={\bigcup }_{i=1}^t{K}_{n_i}$ with ${\sum }_{i=1}^t{n}_i=n-1$ , then we write $G=G{C}_n(n_1,n_2,...,n_t)$ and call u the center of G. If $n_i$ appears $p_i>1$ times in $G{C}_n(n_1,n_2,...,n_t)$ , then we use $n_i^{(p_i)}$ in the notation. As an example, $G{C}_{12}(3,3,2,2,1)$ can also be denoted by $G{C}_{12}(3^{(2)},2^{(2)},1)$ . In particular, the star $S_n$ is simply $G{C}_n(1^{(n-1)})$ . A friendship graph $F_k=G{C}_{2k+1}(2^{(k)})$ of order $2k+1$ consists of k triangles which intersect in a single vertex. Denote by ${\mathcal{C}}_{n,k}$ and ${\mathcal{B}}_{n,k}$ the set of cacti of order n with k cycles and the set of block graphs of order n with k blocks, respectively.

The paper is organized as follows. In Sect. 2, we introduce some preliminary observations, either previously established or proven directly. In Sect. 3, the extremal graphs in ${\mathcal{C}}_{n,k}$ that maximize the number of subtrees are determined. Then, in Sect. 4, graphs in ${\mathcal{B}}_{n,k}$ with maximum number of subtrees are characterized. As it turns out, our methods work also for the number of connected subgraphs (for trees, this is clearly equal to the number of subtrees, but the two differ for general graphs). The extremal graphs also turn out to be exactly the graphs with minimum Wiener index in ${\mathcal{C}}_{n,k}$ and ${\mathcal{B}}_{n,k}$ , respectively. This provides further evidence of the aforementioned correlation. We conclude the paper in Sect. 5 and state a general problem related to the negative correlation between the number of subtrees and the Wiener index.

We start with some simple observations, most of which are trivial. Some of them can also readily be found in the literature.

If G is a disconnected graph with t components $G_1,G_2,...,G_t$ , then we have

1 $$\begin{array}{c}\hfill N(G)=\sum _{i=1}^{t}N(G_i).\end{array}$$

Graph

Also, for any vertex $v\in V(G)$ , we have

2 $$\begin{array}{c}\hfill N(G)=N(v,G)+N(\overline{v},G)\end{array}$$

Graph

where $N(\overline{v},G)$ is the number of subtrees that do not contain the vertex v in G.

From the definitions of the Wiener index and the number of subtrees, it is easy to see the following result. We skip the proof.

Let G be a connected graph with two non-adjacent vertices $u,v\in V(G)$ . Then

• $W(G+uv)<W(G)$ ;
• $N(G+uv)>N(G)$ .

For any integer $n\ge 3$ , we denote by ${\mathcal{G}}_n^2$ the set of graphs of order n with diameter 2. The following result on the Wiener index of graphs in ${\mathcal{G}}_n^2$ will be needed later.

([[22]]) If G is a graph in ${\mathcal{G}}_n^2$ with m edges, then $W(G)=n(n-1)-m$ .

([[18]]) Let T be a tree of order $n\ge 4$ . Then we have

$$\begin{array}{c}\hfill \left(\genfrac{}{}{0pt}{}{n+1}{2}\right)\le N(T)\le 2^{n-1}+n-1,\end{array}$$

Graph

where equality holds in the left inequality if and only if $T\cong P_n$ and equality holds in the right inequality if and only if $T\cong S_n$ .

([[24]]) Let G be a connected graph with a cut vertex $v\in V(G)$ and assume that G is the union of two subgraphs $G_1$ and $G_2$ whose only common vertex is v. Then $N(G)=N(G_1)+N(G_2)-1+\left(N,(,v,,,G_1,),-,1\right)\left(N,(,v,,,G_2,),-,1\right)$ .

Let $F_k$ with $k>1$ be a friendship graph of order $2k+1$ where $v\in V(F_k)$ is the vertex of maximum degree. Then $N(F_k)=3k+6^k$ and $N(v,F_k)=6^k$ .

From the structure of $F_k$ and Eq. (1), we have $N(\overline{v},F_k)=kN(P_2)=3k$ .

Moreover, we have

$$\begin{array}{c}\hfill N(v,F_k)=6^k,\end{array}$$

Graph

since each of the k triangles has six subtrees containing v.

The conclusion $N(F_k)=3k+6^k$ then follows from Eq. (2). $\square$

In this section we will characterize the cactus in ${\mathcal{C}}_{n,k}$ with the maximum number of subtrees. First we establish two technical observations.

Let G be a connected graph with two distinct cut vertices $u,v\in V(G)$ . Let $G_1$ , $G_2$ and $G_3$ be three subgraphs of G such that $V(G_1)\cap V(G_2)=\{u\}$ , $V(G_2)\cap V(G_3)=\{v\}$ and $V(G)=V(G_1)\cup V(G_2)\cup V(G_3)$ . Let $G_v^{\ast }$ be a graph obtained from G by identifying the vertex u of $G_1$ with the vertex $v\in V(G_2)\cap V(G_3)$ , as shown in Fig. 1, and let $G_u^{\ast }$ be defined similarly. Then

• ([[13]]) $W(G)>W(G_v^{\ast })$ or $W(G)>W(G_u^{\ast })$ ;
• $N(G)<N(G_v^{\ast })$ or $N(G)<N(G_u^{\ast })$ .

We only need to prove (ii). Applying Lemma 2.4 to the structures of G and $G_v^{\ast }$ , we have

$$\begin{array}{cc}\hfill N(G)=& N(G_1)+N(G_2)+N(G_3)-2+[N_G(u,G_1)-1][N_G(u,G_2)-1]\hfill \\ \hfill & +[N_G(v,G_2)-1][N_G(v,G_3)-1]\hfill \\ \hfill & +N(u,v;G_2)[N_G(u,G_1)-1][N_G(v,G_3)-1],\hfill \end{array}$$

Graph

and

$$\begin{array}{cc}\hfill N(G_v^{\ast })=& N(G_1)+N(G_2)+N(G_3)-2+[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_2)-1]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_3)-1]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_2)-1][N_{G_v^{\ast }}(v,G_3)-1]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_2)-1][N_{G_v^{\ast }}(v,G_3)-1].\hfill \end{array}$$

Graph

Graph: Fig. 1 Graphs G, Gu∗ and Gv∗

Note that $N_G(u,G_1)=N_{G_v^{\ast }}(v,G_1)>1$ and $N_G(v,G_i)=N_{G_v^{\ast }}(v,G_i)>1$ for $i\in \{2,3\}$ since u, v are two distinct cut vertices in G. Setting ${\mathrm{\Delta }}_v=N(G_v^{\ast })-N(G)$ , we have

$$\begin{array}{cc}\hfill {\mathrm{\Delta }}_v=& [N_G(u,G_1)-1][N_G(v,G_2)-N_G(u,G_2)]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_3)-1]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_1)-1][N_G(v,G_2)-1][N_{G_v^{\ast }}(v,G_3)-1]\hfill \\ \hfill & -N(u,v;G_2)[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_3)-1]\hfill \\ \hfill =& [N_G(u,G_1)-1][N_G(v,G_2)-N_G(u,G_2)]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_3)-1]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_3)-1][N_G(v,G_2)-N(u,v;G_2)-1]\hfill \\ \hfill \ge & [N_G(u,G_1)-1][N_G(v,G_2)-N_G(u,G_2)]\hfill \\ \hfill & +[N_{G_v^{\ast }}(v,G_1)-1][N_{G_v^{\ast }}(v,G_3)-1].\hfill \end{array}$$

Graph

Note that the last inequality holds because $N_G(v,G_2)=N(v,G_2)>N(u,v;G_2)$ .

Similarly, setting ${\mathrm{\Delta }}_u=N(G_u^{\ast })-N(G)$ , we get

$$\begin{array}{cc}\hfill {\mathrm{\Delta }}_u\ge & [N_G(v,G_3)-1][N_G(u,G_2)-N_G(v,G_2)]\hfill \\ \hfill & +[N_{G_u^{\ast }}(u,G_1)-1][N_{G_u^{\ast }}(u,G_3)-1].\hfill \end{array}$$

Graph

If $N_G(u,G_2)=N_G(v,G_2)$ , we have ${\mathrm{\Delta }}_u>0$ and ${\mathrm{\Delta }}_v>0$ since $G_1$ and $G_3$ contain at least two distinct vertices each. Otherwise, $N_G(u,G_2)\ne N_G(v,G_2)$ . Then we have $N_G(u,G_2)>N_G(v,G_2)$ or $N_G(v,G_2)>N_G(u,G_2)$ , which implies that ${\mathrm{\Delta }}_u>0$ or ${\mathrm{\Delta }}_v>0$ respectively. This completes the proof. $\square$

Let G be a graph obtained by identifying a vertex of a connected graph $G_0$ with a vertex of a cycle $C_t$ ( $t>3$ ) so that $V(G_0)\cap V(C_t)=\{v\}$ . Let $G^{\prime }$ be another graph obtained by identifying the vertex v of $G_0$ with the center of $G{C}_t(2,1^{(t-3)})$ so that $V(G_0)\cap V(G{C}_t(2,1^{(t-3)}))=\{v\}$ , as shown in Fig. 2. Then $N(G)<N(G^{\prime })$ .

Graph: Fig. 2 Graphs G (left) and G′ (right)

First note that $N(C_t)=t^2$ , $N(v,C_t)=\left(\genfrac{}{}{0pt}{}{t+1}{2}\right)$ , and $N(v,G{C}_t(2,1^{(t-3)}))=6·2^{t-3}$ . By Eq. (2), we have $N(G{C}_t(2,1^{(t-3)}))=6·2^{t-3}+t$ . By Lemma 2.4 and the structure of G and $G^{\prime }$ , we have

$$\begin{array}{cc}\hfill N(G^{\prime })-N(G)=& N(G_0)+N(G{C}_t(2,1^{(t-3)}))-1\hfill \\ \hfill & +[N(v,G_0)-1][N(v,G{C}_t(2,1^{(t-3)}))-1]\hfill \\ \hfill & -N(G_0)-N(C_t)+1-[N(v,G_0)-1][N(v,C_t)-1]\hfill \\ \hfill =& 6·2^{t-3}+t-t^2\hfill \\ \hfill & +[N(v,G_0)-1][N(v,G{C}_t(2,1^{(t-3)}))-N(v,C_t)]\hfill \\ \hfill \ge & [N(v,G_0)-1][N(v,G{C}_t(2,1^{(t-3)}))-N(v,C_t)]\hfill \\ \hfill \ge & 6·2^{t-3}-\frac{1}{2}t(t+1)>0.\hfill \end{array}$$

Graph

Here the last inequality holds by induction on $t\ge 4$ . This completes the proof.

$\square$

Now we are ready to prove the main result in this section.

For any graph $G\in {\mathcal{C}}_{n,k}$ with $n\ge 2k+1$ , we have

$$\begin{array}{c}\hfill N(G)\le 6^k·2^{n-2k-1}+n+k-1\end{array}$$

Graph

with equality if and only if $G\cong G{C}_n(2^{(k)},1^{(n-2k-1)})$ .

Let $G\in {\mathcal{C}}_{n,k}$ be a graph that attains the maximum of N(G). If $G\cong G{C}_n(2^{(k)},1^{(n-2k-1)})$ , then G can be viewed as a graph obtained by identifying the vertex v of maximum degree in $F_k$ with the center of a star $S_{n-2k}$ . By Lemmas 2.3, 2.4 and 2.5, we have

$$\begin{array}{cc}\hfill N(G{C}_n(2^{(k)},1^{(n-2k-1)}))=& N(F_k)+N(S_{n-2k})-1\hfill \\ \hfill & +[N(v,F_k)-1][N(v,S_{n-2k})-1]\hfill \\ \hfill =& 3k+6^k+2^{n-2k-1}+n-2k-2\hfill \\ \hfill & +(6^k-1)(2^{n-2k-1}-1)\hfill \\ \hfill =& 6^k·2^{n-2k-1}+n+k-1.\hfill \end{array}$$

Graph

Otherwise, suppose $G\ncong G{C}_n(2^{(k)},1^{(n-2k-1)})$ . By the extremality of N(G) and Lemma 3.1 (ii), there exists only one cut vertex in G. Since $G\ncong G{C}_n(2^{(k)},1^{(n-2k-1)})$ , there must be at least one induced cycle $C_t$ with $t>3$ in G. Then Lemma 3.2 leads to a contradiction, which completes the proof. $\square$

Since ${\mathcal{C}}_{n,1}$ is just the set of unicyclic graphs of order n, the result below follows immediately from Theorem 3.3.

([[3]]) For any unicyclic graph G of order $n>3$ , we have

$$\begin{array}{c}\hfill N(G)\le n+6·2^{n-3}\end{array}$$

Graph

with equality if and only if $G\cong G{C}_n(2,1^{(n-3)})$ .

Let C(G) denote the number of connected subgraphs in a graph G. Lemmas 3.1 and 3.2 hold for C(G) instead of N(G) using the same reasoning. Therefore we also get an analogue of Theorem 3.3 whose full proof is omitted.

For any graph $G\in {\mathcal{C}}_{n,k}$ with $n\ge 2k+1$ , we have

$$\begin{array}{c}\hfill C(G)\le 7^k·2^{n-2k-1}+n+k-1\end{array}$$

Graph

with equality if and only if $G\cong G{C}_n(2^{(k)},1^{(n-2k-1)})$ .

In [[13]], it is shown that the graph $G{C}_n(2^{(k)},1^{(n-2k-1)})$ also uniquely attains the minimum Wiener index among all graphs in ${\mathcal{C}}_{n,k}$ .

In this section we focus on the extremal graphs in ${\mathcal{B}}_{n,k}$ with maximum number of subtrees and minimum Wiener index, respectively. Identical extremal graphs provide yet another example of the known negative correlation between these two graph invariants.

A sequence ${(a_n)}_{n\ge 0}$ is called convex (log-convex, resp.) if $a_{n+2}+a_n\ge 2a_{n+1}$ ( $log{a}_{n+2}+log{a}_n\ge 2log{a}_{n+1}$ , resp.) for every integer $n\ge 0$ . If strict inequality holds for all n, then the sequence is called strictly convex (log-convex, resp.). Any positive log-convex sequence ${(a_n)}_{n\ge 0}$ is also convex, since we have $a_{n+2}^2+a_n^2+2a_n{a}_{n+2}\ge 4a_n{a}_{n+2}\ge 4a_{n+1}^2$ from $a_{n+2}{a}_n\ge a_{n+1}^2$ , that is, $a_{n+2}+a_n\ge 2a_{n+1}$ .

We will make use of the Davenport–Pólya Theorem ([[8]], see also [[14], p. 455]), which states that the binomial convolution ${\sum }_{k=0}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)a_k{b}_{n-k}$ of two log-convex sequences ${(a_n)}_{n\ge 0}$ and ${(b_n)}_{n\ge 0}$ is again log-convex. In particular (taking $b_n=1$ for all n), if ${(a_n)}_{n\ge 0}$ is a log-convex sequence, then so is the sequence given by $c_n={\sum }_{k=0}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)a_k$ . If ${(a_n)}_{n\ge 0}$ is even strictly log-convex, then so is ${(c_n)}_{n\ge 0}$ .

We are particularly interested in two sequences related to subtree counting: for a complete graph $K_n$ and any vertex $v\in V(K_n)$ , we set $a_n=N(K_n)$ and $b_n=N(v,K_n)$ . Note that $a_n=N(K_n)={\sum }_{t=1}^n\left(\genfrac{}{}{0pt}{}{n}{t}\right)t^{t-2}$ , since any complete graph $K_t$ has $t^{t-2}$ spanning trees ([[5]]), and $b_n=N(v,K_n)={\sum }_{t=1}^n\left(\genfrac{}{}{0pt}{}{n-1}{t-1}\right)t^{t-2}$ ([[24]]) for the same reason.

It is easy to verify that the sequence $c_n=n^{n-2}$ is strictly log-convex for $n\ge 1$ , for example by considering the second derivative of $f(x)=log(x^{x-2})=(x-2)logx$ . So the Davenport–Pólya Theorem yields

The sequence ${(a_n)}_{n\ge 1}$ given by $a_n={\sum }_{k=1}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)k^{k-2}$ is strictly convex.

The sequence ${(b_n)}_{n\ge 1}$ given by $b_n={\sum }_{k=1}^n\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)k^{k-2}$ is strictly $log$ -convex.

Given two non-increasing sequences ${(a_i)}_{i=1}^n$ and ${(b_i)}_{i=1}^n$ , we say that ${(a_i)}_{i=1}^n$ is majorized by ${(b_i)}_{i=1}^n$ , denoted by ${(a_i)}_{i=1}^n\prec {(b_i)}_{i=1}^n$ , if the following statements hold:

• ${\sum }_{i=1}^n{a}_i={\sum }_{i=1}^n{b}_i$ ;
• ${\sum }_{i=1}^s{a}_i\le {\sum }_{i=1}^s{b}_i$ for $1\le s<n$ .

An n-dimensional function F is called Schur-convex if $F(a_1,a_2,...,a_n)\le F(b_1,b_2,...,b_n)$ whenever ${(a_i)}_{i=1}^n$ is majorized by ${(b_i)}_{i=1}^n$ . It is known (see e.g. [[16], p.259, Theorem B]) that $F(x_1,x_2,...,x_n)={\sum }_{i=1}^{n}f(x_i)$ is Schur-convex if f is convex. Since every convex sequence can be extended to a convex function by linear interpolation, the following is immediate.

Let ${(a_i)}_{i=1}^n$ and ${(b_i)}_{i=1}^n$ be two non-increasing positive integer sequences such that ${(a_i)}_{i=1}^n\prec {(b_i)}_{i=1}^n$ , and let ${(x_j)}_{j\ge 1}$ be a convex (log-convex, resp.) sequence. Then ${\sum }_{j=1}^n{x}_{a_j}\le {\sum }_{j=1}^n{x}_{b_j}$ ( ${\prod }_{j=1}^n{x}_{a_j}\le {\prod }_{j=1}^n{x}_{b_j}$ , resp.). If the sequence is even strictly convex (log-convex, resp.), then strict inequality holds unless ${(a_i)}_{i=1}^n$ and ${(b_i)}_{i=1}^n$ coincide.

The following statement is easy to prove from the definition of majorization.

Let ${(a_i)}_{i=1}^k$ be a non-increasing sequence of positive integers with ${\sum }_{i=1}^k{a}_i=n-1$ . Let the sequence ${(b_i)}_{i=1}^k$ be defined by $b_1=n-k$ and $b_j=1$ for $2\le j\le k$ . Then we have ${(a_i)}_{i=1}^k\prec {(b_i)}_{i=1}^k$ .

We are now ready to identify the extremal graph with maximum number of subtrees in ${\mathcal{B}}_{n,k}$ .

For any graph $G\in {\mathcal{B}}_{n,k}$ , we have

$$\begin{array}{c}\hfill N(G)\le \sum _{t=1}^{n-k}\left(\genfrac{}{}{0pt}{}{n-k}{t}\right)t^{t-2}+2^{k-1}\sum _{t=1}^{n-k+1}\left(\genfrac{}{}{0pt}{}{n-k}{t-1}\right)t^{t-2}+k-1\end{array}$$

Graph

with equality if and only if $G\cong G{C}_n(n-k,1^{(k-1)})$ .

Let $G\in {\mathcal{B}}_{n,k}$ be a graph that attains the maximum of N(G). By Lemma 3.1 (ii) and Lemma 2.1 (ii), we can assume that G is a generalized complete graph $G=G{C}_n(n_1,n_2,...,n_k)$ with $n_1\ge n_2\ge \cdots \ge n_k\ge 1$ and ${\sum }_{i=1}^k{n}_i=n-1$ . Let v be the center of G. Recall that $a_n=N(K_n)={\sum }_{t=1}^n\left(\genfrac{}{}{0pt}{}{n}{t}\right)t^{t-2}$ and $b_n=N(u,K_n)={\sum }_{t=1}^n\left(\genfrac{}{}{0pt}{}{n-1}{t-1}\right)t^{t-2}$ for any vertex $u\in V(K_n)$ . We have

$$\begin{array}{cc}\hfill N(G)& =N(v,G)+N(\overline{v},G)=\prod _{i=1}^{k}N(v,K_{n_i+1})+\sum _{i=1}^{k}N(K_{n_i})\hfill \\ \hfill & =\prod _{i=1}^k{b}_{n_i+1}+\sum _{i=1}^k{a}_{n_i}.\hfill \end{array}$$

Graph

Combining Lemmas 4.1, 4.2, 4.3 and 4.4, we conclude that N(G) attains its maximum uniquely when $n_1=n-k$ and $n_2=n_3=\cdots =n_k=1$ with the corresponding maximum

$$\begin{array}{cc}\hfill a_{n-k}+b_2^{k-1}{b}_{n-k+1}+(k-1)a_1& =\sum _{t=1}^{n-k}\left(\genfrac{}{}{0pt}{}{n-k}{t}\right)t^{t-2}+2^{k-1}\hfill \\ \hfill & \times \sum _{t=1}^{n-k+1}\left(\genfrac{}{}{0pt}{}{n-k}{t-1}\right)t^{t-2}+k-1.\hfill \end{array}$$

Graph

This completes the proof. $\square$

Recall that C(G) is the number of connected subgraphs in a graph G. For a vertex $v\in V(G)$ , we denote by C(v, G) and $C(\overline{v},G)$ the number of connected subgraphs that contain v and do not contain v, respectively. As we will see, the approach that was used to prove Theorem 4.5 can also be used to prove a corresponding result for C(G). This result will be presented in the following. Let $h_n$ denote the number of connected spanning subgraphs of $K_n$ , that is, the number of connected labeled graphs of order n, and set $f_n=C(K_n)$ and $g_n=C(v,K_n)$ for a vertex v of $K_n$ . Note that $f_n=C(K_n)={\sum }_{t=1}^n\left(\genfrac{}{}{0pt}{}{n}{t}\right)h_t$ and $g_n=C(v,K_n)={\sum }_{t=1}^n\left(\genfrac{}{}{0pt}{}{n-1}{t-1}\right)h_t$ .

In order to follow the same approach as for the number of subtrees, we first verify that ${(h_n)}_{n\ge 1}$ is a strictly log-convex sequence.

The sequence ${(h_n)}_{n\ge 1}$ is strictly log-convex.

It is known that (see also [[10], Sect. 9.5] for more precise asymptotics)

$$\begin{array}{c}\hfill 2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}-\frac{1}{2}\sum _{k=1}^{n-1}\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{\left(\genfrac{}{}{0pt}{}{k}{2}\right)+\left(\genfrac{}{}{0pt}{}{n-k}{2}\right)}\le h_n\le 2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}.\end{array}$$

Graph

The upper bound is trivial, as $2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}$ is simply the number of all labeled graphs of order n. The lower bound follows by noticing that every disconnected graph can be split into a graph of order k and a graph of order $n-k$ for some k. Note that

$$\begin{array}{cc}\hfill \frac{1}{2}\sum _{k=1}^{n-1}\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{\left(\genfrac{}{}{0pt}{}{k}{2}\right)+\left(\genfrac{}{}{0pt}{}{n-k}{2}\right)}& =2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}·\sum _{k=1}^{n-1}\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{-k(n-k)-1}\hfill \\ \hfill & =2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}·[n{2}^{1-n}+\sum _{k=2}^{n-2}\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{-k(n-k)-1}]\hfill \\ \hfill & \le 2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}·[n{2}^{1-n}+\sum _{k=0}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{-2(n-2)-1}]\hfill \\ \hfill & =2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}·[n{2}^{1-n}+2^{3-n}]=2(n+4)2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)-n}.\hfill \end{array}$$

Graph

Therefore, we have $2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}[1-2(n+4)2^{-n}]\le h_n\le 2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}$ . It follows that

$$\begin{array}{cc}\hfill \frac{h_{n-1}{h}_{n+1}}{h_n^2}& \ge 2^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)+\left(\genfrac{}{}{0pt}{}{n-1}{2}\right)-2\left(\genfrac{}{}{0pt}{}{n}{2}\right)}[1-2(n+3)2^{1-n}][1-2(n+5)2^{-1-n}]\hfill \\ \hfill & =2[1-(4n+12)2^{-n}][1-(n+5)2^{-n}]\hfill \\ \hfill & \ge 2[1-(4n+12)2^{-n}-(n+5)2^{-n}]\hfill \\ \hfill & =2-(10n+34)2^{-n},\hfill \end{array}$$

Graph

which is greater than 1 for $n\ge 7$ . Moreover, the strict log-convexity of ${(h_n)}_{n\ge 1}$ can be directly verified for smaller values of n. This completes the proof. $\square$

Now the following lemmas follow once again from the Davenport–Pólya Theorem in the same way as Lemmas 4.1 and 4.2.

The sequence ${(f_n)}_{n\ge 1}$ given by $f_n={\sum }_{k=1}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)h_k$ is strictly convex.

The sequence ${(g_n)}_{n\ge 1}$ given by $g_n={\sum }_{k=1}^n\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)h_k$ is strictly $log$ -convex.

We finally obtain the following analogue of Theorem 4.5 with a completely analogous proof.

For any graph $G\in {\mathcal{B}}_{n,k}$ , we have $C(G)\le f_{n-k}+2^{k-1}{g}_{n-k+1}+k-1$ with equality if and only if $G\cong G{C}_n(n-k,1^{(k-1)})$ .

We now move on to consider the minimum Wiener index of a graph in ${\mathcal{B}}_{n,k}$ . The following result comes from the fact that ${(n^2)}_{n\ge 1}$ is a strictly convex sequence.

Let $n_1\ge n_2\ge ...\ge n_k$ be positive integers with ${\sum }_{i=1}^k{n}_i=t$ . Then

$$\begin{array}{c}\hfill \sum _{i=1}^k{n}_i^2\le {(t-k+1)}^2+k-1\end{array}$$

Graph

with equality if and only if $n_1=t-k+1$ and $n_j=1$ for $j\in \{2,3,...,k\}$ .

For any graph $G\in {\mathcal{B}}_{n,k}$ , we have

$$\begin{array}{c}\hfill W(G)\ge \frac{1}{2}[n^2+(2k-3)n-(k+2)(k-1)]\end{array}$$

Graph

with equality if and only if $G\cong G{C}_n(n-k,1^{(k-1)})$ .

Let $G\in {\mathcal{B}}_{n,k}$ be a graph that attains the minimum of W(G). By Lemma 2.1 (i) and Lemma 3.1 (i), G must be a generalized complete graph of the form $G=G{C}_n(n_1,n_2,...,n_k)$ with $n_1\ge n_2\ge \cdots \ge n_k\ge 1$ and ${\sum }_{i=1}^k{n}_i=n-1$ . Note that $G=G{C}_n(n_1,n_2,...,n_k)$ has diameter 2, and that its number of edges is

$$\begin{array}{c}\hfill m=\sum _{i=1}^k\left(\genfrac{}{}{0pt}{}{n_i+1}{2}\right)=\frac{1}{2}\sum _{i=1}^k{n}_i^2+\frac{n-1}{2}.\end{array}$$

Graph

Then, by Lemmas 2.2 and 4.10, we have

$$\begin{array}{cc}\hfill W(G)=& n(n-1)-m\hfill \\ \hfill \ge & n(n-1)-\frac{1}{2}[{(n-k)}^2+k-1+n-1]\hfill \\ \hfill =& \frac{1}{2}[n^2+(2k-3)n-(k+2)(k-1)]\hfill \end{array}$$

Graph

with equality holding if and only if $(n_1,n_2,...,n_k)=(n-k,1^{(k-1)})$ , that is, $G\cong G{C}_n(n-k,1^{(k-1)})$ . $\square$

As a corollary, we obtain the maximum number of subtrees and connected subgraphs as well as the minimum of the Wiener index over all graphs with n vertices and k blocks. By Lemma 2.1, all blocks of the graphs that attain these must be complete. By Theorems 4.5, 4.9 and 4.11, we have the following more general statement.

Let G be a connected graph of order n with k blocks. Then

• $N(G)\le {\sum }_{t=1}^{n-k}\left(\genfrac{}{}{0pt}{}{n-k}{t}\right)t^{t-2}+2^{k-1}{\sum }_{t=1}^{n-k+1}\left(\genfrac{}{}{0pt}{}{n-k}{t-1}\right)t^{t-2}+k-1$ with equality if and only if $G\cong G{C}_n(n-k,1^{(k-1)})$ ;
• $C(G)\le {\sum }_{t=1}^{n-k}\left(\genfrac{}{}{0pt}{}{n-k}{t}\right)h_t+2^{k-1}{\sum }_{t=1}^{n-k+1}\left(\genfrac{}{}{0pt}{}{n-k}{t-1}\right)h_t+k-1$ with equality if and only if $G\cong G{C}_n(n-k,1^{(k-1)})$ ;
• $W(G)\ge \frac{1}{2}[n^2+(2k-3)n-(k+2)(k-1)]$ with equality if and only if $G\cong G{C}_n(n-k,1^{(k-1)})$ .

In this paper we characterized the extremal graphs with the maximum number of subtrees or connected subgraphs among cacti and block graphs with a given number of vertices and cycles resp. blocks. It was also shown that the extremal structures among block graphs coincide with those minimizing the Wiener index. Along with previously established observations on the Wiener index [[13]], these extremal results provide more evidence of the negative correlation between the number of subtrees and the Wiener index, as mentioned in Sect. 1. Along this line, it would be interesting to find other parameters, say $\alpha$ (e.g., the number of certain substructures), of a connected graph G of order n, such that in the set ${\mathcal{G}}_{n,\alpha }$ of connected graphs of order n with given structural parameter $\alpha$ , the extremal graphs maximizing (minimizing, resp.) the number of subtrees coincide with the extremal graphs minimizing (maximizing, resp.) the Wiener index.

S. Wagner was supported by the Knut and Alice Wallenberg Foundation. The authors are very grateful to PhD student Zuwen Luo for the helpful discussion with him.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.