In this paper, we only consider connected, simple and undirected graphs and assume that all graphs are connected, and refer to Bondy and Murty [2] for notation and terminologies used but not defined here.

Let $G=(V_G, E_G)$ be a graph with vertex set $V_G$ and edge set $E_G$. $G-v, G-uv$ denote the graph obtained from $G$ by deleting vertex $v\in V_G$ or edge $uv\in E_G$, respectively (this notation is naturally extended if more than one vertex or edge is deleted). Similarly, $G+uv$ is obtained from $G$ by adding an edge $uv\notin E_G$. For $v\in V_G$, let $N_G(v)$($N(v)$ for short) denote the set of all the adjacent vertices of $v$ in $G$ and $d(v)=|N_G(v)|$, the degree of $v$ in $G$.

A bipartite graph $G$ is a simple graph, whose vertex set $V_G$ can be partitioned into two disjoint subsets $V_1$ and $V_2$ such that every edge of $G$ joins a vertex of $V_1$ with a vertex of $V_2$. A bipartite graph in which every two vertices from different partition classes are adjacent is called complete, which is denoted by $K_{m, n}$, where $m=|V_1|, n=|V_2|$.

The distance $d(u, v)$ between vertices $u$ and $v$ in $G$ is defined as the length of a shortest path between them. The diameter of $G$ is the maximal distance between any two vertices of $G$. Let ${B}_n^d$ be the class of all bipartite graphs of order $n$ with diameter $d$.

Let $S_k=S_k(G)$ be the sum of $k$-power of distances between all pairs of vertices of $G$, which is denoted by

$ \begin{equation*} S_k=S_k(G)=\sum\limits_{u, v\in V_G}d_G^k(u, v)=\frac{1}{2}\sum\limits_{v\in V_G}H_G(v), \end{equation*} $

where $H_G(v)$ is the sum of $k$-power of all diatances from $v$ in $G$.

When $k=1$, $S_k$ is Wiener index. The Wiener index is popular in chemical literatures. This quantity was introduced by Mustapha Aouchich and Pierre Hansen in [1] and was extensively studied in the monograph. Recently, $S_2(G)$ is applied to the research of distance spectral radius. Zhou and Trinajstić [19] proved an upper bound using the order $n$ in addition to the sum of the squares of the distances $S_2(G)$, see [18, 20]. They also proved a lower bound on the distance spectral radius of a graph using only $S_2(G)$. As a continuance of it, in this paper, we determine the extremal graphs with the minimal $S_k(G)$ for the class of all connected $n$-vertex bipartite graphs of diameter $d$. For surveys and some up-to-date papers related to Wiener index of trees and line graphs, see [7, 9, 11-15, 17] and [3, 6, 8, 10, 16], respectively.

In this paper we study the quantity $S_k$ in the case of $n$-vertex bipartite graphs, which is an important class of graphs in graph theory. Based on the structure of bipartite graphs, sharp bounds on $S_k$ among ${B}_n^d$ are determined. The corresponding extremal graph is also identified.

Further on we need the following lemma, which is the direct consequence of the definition of $S_k$.

Lemma 1.1 Let $G$ be a connected graph of order $n$ and not isomorphic to $K_n$. Then for each edge $e\in \overline{G}, S_k(G)>S_k(G+e)$.

Let $G$ be a graph in ${B}_n^d$. Clearly there exists a partition $V_0, V_1, \cdots, V_d$ of $V_G$ such that $|V_0|=1$ and $d(u, v)=i$ for each vertex $v\in V_i$ and $u\in V_0~(i=0, 1, \cdots, d)$. We call $V_i$ a block of $V_G$. Two blocks $V_i, V_j$ of $V_G$ are adjacent if $|i-j|=1$. For convenience, let $|V_i|=l_i$ throughout this section.

Lemma 2.1 [15] For any graph $G\in{B}_n^d$ with the above partition of $V_G$, $G[V_i]$ induces an empty graph (i.e., containing no edge) for each $i\in(i=0, 1, \cdots, d)$.

Given a complete bipartite graph $K_{\lfloor\frac{n-d+3}{2}\rfloor, \lceil\frac{n-d+3}{2}\rceil}$ with bipartition $(X, Y)$ satisfying $|Y|=\lceil\frac{n-d+3}{2}\rceil$ and $|X|=\lfloor\frac{n-d+3}{2}\rfloor\geq2$, choose a vertex $x$ (resp. $y$) in $X$ (resp. $Y$) and let $G'=K_{\lfloor\frac{n-d+3}{2}\rfloor, \lceil\frac{n-d+3}{2}\rceil}-xy, $ where $G'$ is depicted in Figure 1. Let $G^\ast$ be the graph obtained from $G'$ by attaching paths $P_{\frac{d-3}{2}}$ and $P_{\frac{d-3}{2}}$ at $x$ and $y$, respectively. It is routine to check that $\hat{G}[p, q]\in{B}_n^d$ for odd $d$.

Given a complete bipartite graph $K_{p, q}$ with bipartition $(X, Y)$ satisfying $|X|=p\geq3, |Y|=q\geq2$, and $p+q=n-d+4$, choose two different vertices, say $x, y$ in $X$ and let

$ \begin{equation*} G''=K_{p, q}-\{xw:w\in V'\subsetneq Y\}-\{yw':w'\in Y\backslash V'\}, \end{equation*} $

where $G''$ is depicted in Figure 1. Let $\hat{G}[p, q]$ be the graph obtained from $G''$ by attaching paths $P_\frac{d-4}{2}$ and $P_\frac{d-4}{2}$ at $x$ and $y$, respectively. It is routine to check that $\hat{G}[p, q]\in{B}_n^d$ for even $d$. Set $\mathbb{B}=\{\hat{G}[p, q]:p+q=n-d+4, |(p-2)-q|\leq1\}.$

Theorem 2.2 Let $G$ be in ${B}_n^d$ with the minimum $S_k(G)$.

(ⅰ) If $d=2$, then $G\cong K_{\lfloor\frac{n}{2}\rfloor, \lceil\frac{n}{2}\rceil}$.

(ⅱ) If $d\geq3$, then $G\cong G^\ast$ for odd $d$ and $G\in \mathbb{B}$ for even $d$, where $G^\ast$ and $\mathbb{B}$ are defined as above.

Proof Choose $G\in{B}_n^d$ with bipartition $(X, Y)$ such that $S_k(G)$ is as small as possible.

(ⅰ) If $d=2$, then by Lemma 1.1, $G\cong K_{n-t, t}$, where $t\geq 2$ or $n-t\geq2$. Let $|X|=n-t, |Y|=t$. Then it is routine to check that, for all $x$ (resp. $y$) in $X$ (resp. $Y$), one has

$ H_G(x)=2^kn-(2^k-1)t-2^k, H_G(y)=(2^k-1)t+n-2^k, $

which gives

$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) S_k(K_{n-t, t}) &=& \frac{1}{2}\left(\sum\limits_{x\in X}H_G(x)+\sum\limits_{y\in Y}H_G(y)\right) \\ &=& \frac{1}{2}(n-t)(2^kn-(2^k-1)t-2^k)+\frac{1}{2}t((2^k-1)t+n-2^k)\\ &=& \frac{1}{2}\left(2^kn^2+2(2^k-1)t^2-2(2^k-1)nt-2^kn\right).\\ &=& 2^{k-1}n^2+(2^k-1)t^2-(2^k-1)nt-2^{k-1}n. \end{eqnarray*} $

If $n$ is odd, then $S_k(K_{n-t, t})\geq\frac{2^k+1}{4}n^2-2^{k-1}n+\frac{2^k-1}{4}$ with equality if and only if $t=\frac{n-1}{2}$, or $t=\frac{n+1}{2}$, i.e. $G\cong K_{\lfloor\frac{n}{2}\rfloor, \lceil\frac{n}{2}\rceil}$; And if $n$ is even, then $S_k(K_{n-t, t})\geq\frac{2^k+1}{4}n^2-2^{k-1}n$ with equality if and only if $t=\frac{n}{2}$, i.e., $G\cong K_{\frac{n}{2}, \frac{n}{2}}$, as desired.

(ⅱ) First we show the following facts.

Fact 1 $G[V_{i-1}, V_i]$ induces a complete bipartite subgraph for each $i\in (0, 1, \cdots d)$, and $|V_d|=1$ for $d\geq3$.

Proof of Fact 1 The first part follows directly from Lemmas 1.1 and 2.1. So in what follows, we prove the second part.

Let $d\geq3$, $z\in V_d$ and $w\in V_{d-3}$. If $|V_d|>2$, then $G+zw\in{B}_n^d$ and $V_0\cup V_1\cup \big(V_{d-3}\backslash\{w\}\big)\cup V_{d-2}\cup $ $\big(V_{d-1}\cup\{w\}\big)\cup V_d$ is a partition of $V_{G+zw}$. By Lemma 1.1 $S_k(G+zw)<S_k(G)$, a contradiction.

This completes the proof of Fact 1.

Fact 2 Consider the vertex partition $V_G=V_0\cup V_1\cup\cdots\cup V_d$ of $G$.

(ⅰ) If $d$ is odd, then

$ |V_0|=|V_1|=\cdots=\left|V_{\frac{d-1}{2}-1}\right|=\left|V_{\frac{d-1}{2}+2}\right|=\cdots=|V_{d-1}|=|V_d|=1,\\ \left||V_{\frac{d-1}{2}}|-|V_{\frac{d-1}{2}+1}|\right|\leq1. $

(ⅱ) If $d$ is even, then

$ |V_0|=|V_1|=\cdots=\left|V_{\frac{d}{2}-2}\right|=\left|V_{\frac{d}{2}+2}\right|=\cdots=|V_{d-1}|=|V_d|=1,\\ \left||V_{\frac{d}{2}}|-(|V_{\frac{d}{2}-1}|+|V_{\frac{d}{2}+1}|)\right|\leq1. $

Proof of Fact 2 (ⅰ) Note that $|V_0|=|V_d|=1$, here we only show that $|V_1|=1$ holds. Similarly, we can also show $|V_2|=\cdots=\left|V_{\frac{d-1}{2}-1}\right|=\left|V_{\frac{d-1}{2}+2}\right|=\cdots=|V_{d-1}|=1$, we omit the procedure here.

In fact, if $d=3$, our result is trivial. So we consider that $d\geq5$. If $|V_1|\geq2$, then choose $u\in V_1$ and let $G'=G-v_0u+\{ux:x\in V_4\}$. In fact, the vertex partition of $G'$ is $V_0\cup\big(V_1\backslash\{u\}\big)\cup V_2\cup\big(V_3$ $\cup\{u\}\big)\cup V_4\cup\cdots\cup V_d$, in view of Fact 1 and the choice of $G$, any two of adjacent blocks of $V_{G'}$ induce a complete bipartite subgraph and $|V_d|=1$ for $d\geq5$.

Note that $\sum\limits_{i=4}^d\left((i-1)^k-(i-3)^k\right)l_i\geq\sum\limits_{i=4}^d\left((i-1)^k-(i-3)^k\right)>(3^k-1)$,

$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) H_G(u)&=& H_{G'}(u)+\sum\limits_{i=4}^d\left((i-1)^k-(i-3)^k)\right)l_i-(3^k-1); \\ H_G(v) &=& H_{G'}(v)-(3^k-1), ~~ \forall v\in V_0; \\ H_G(v) &=& H_{G'}(v), ~~\forall v\in \big(V_1\backslash\{u\}\big)\cup V_2\cup V_3;\\ H_G(v) &=& H_{G'}(v)+(i-1)^k-(i-3)^k, ~~\forall v\in V_4\cup V_5\cup\cdots\cup V_d. \end{eqnarray*} $

This gives

$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) &&S_k(G)-S_k(G') =\frac{1}{2}\left(\sum\limits_{v\in V_G}H_G(v)-\sum\limits_{v\in V_{G'}}H_{G'}(v)\right) \\ &=& \frac{1}{2}\left(\sum\limits_{v\in V_0}(H_G(v)-H_{G'}(v))+H_G(u)-H_{G'}(u)\right) +\sum\limits_{i=4}^d\sum\limits_{v\in V_i}(H_G(v)-H_{G'}(v))\\ &=& \frac{1}{2}\bigg[-2(3^k-1)+2\sum\limits_{i=4}^d\left((i-1)^k-(i-3)^k\right)l_i\bigg] \\ &=& \bigg[-(3^k-1)+\sum\limits_{i=4}^d\left((i-1)^k-(i-3)^k\right)l_i\bigg]>0, \end{eqnarray*} $

i.e., $S_k(G)>S_k(G')$, a contradiction to the choice of $G$. Hence, $|V_1|=1$.

Next we show that if $d$ is odd, then $\left||V_{\frac{d-1}{2}}|-|V_{\frac{d-1}{2}+1}|\right|\leq1$. Without loss of generality, we assume that $\left|V_{\frac{d-1}{2}}\right|\geq\left|V_{\frac{d-1}{2}+1}\right|$. Then it suffices to show that $\left|V_{\frac{d-1}{2}}\right|-\left|V_{\frac{d-1}{2}+1}\right|\leq1$. If this is not true, then $|V_{\frac{d-1}{2}}|-|V_{\frac{d-1}{2}+1}|\geq2$. Choose $w\in V_\frac{d-1}{2}$, let

$ G'=G-\left\{ux:x\in V_\frac{d-3}{2}\cup V_\frac{d+1}{2}\right\}+\left\{wy:y\in V_\frac{d-1}{2}\cup V_\frac{d+3}{2}\right\}, $

then the vertex partition of $G'$ is

$ V_0\cup V_1\cup \cdots\cup V_\frac{d-3}{2}\cup\left(V_\frac{d-1}{2}\backslash\{w\}\right)\cup\left(V_\frac{d+1}{2}\cup\{w\}\right)\cup V_\frac{d+3}{2}\cup\cdots\cup V_d $

and each of the two adjacent blocks of $V_{G'}$ induces a complete bipartite graph. By direct calculation, we have

$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) S_k(G')-S_k(G) &=& \left[(|V_\frac{d-1}{2}|-1)+2^k|V_\frac{d+1}{2}|\right]-\left[2^k(|V_\frac{d-1}{2}|-1)+|V_\frac{d+1}{2}|\right] \\ &=& -(2^k-1)\left(|V_\frac{d-1}{2}|-|V_\frac{d+1}{2}|-1\right)\leq-(2^k-1)<0, \end{eqnarray*} $

a contradiction to the choice of $G$.

(ⅱ) By the same discussion as the proof of the first part of (i) as above, we can show that $|V_0|=|V_1|=\cdots=\left|V_{\frac{d}{2}-2}\right|=\left|V_{\frac{d}{2}+2}\right|=\cdots=|V_{d-1}|=|V_d|=1, $ we omit the procedure here.

Now, we show that if $d$ is even, then $\left||V_\frac{d}{2}|-(|V_{\frac{d}{2}-1}|+|V_{\frac{d}{2}+1}|)\right|\leq1$. Without loss of generality, we assume that $\left|V_\frac{d}{2}\right|<\left|V_{\frac{d}{2}-1}\right|+\left|V_{\frac{d}{2}+1}\right|$. Then it suffices to show that

$ \left|V_{\frac{d}{2}-1}\right|+\left|V_{\frac{d}{2}+1}\right|-\left|V_\frac{d}{2}\right|\leq1. $

If this is not true, then $\left|V_{\frac{d}{2}-1}\right|+\left|V_{\frac{d}{2}+1}\right|-\left|V_\frac{d}{2}\right|\geq2.$ It is routine to check that at least one of $V_{\frac{d}{2}-1}$ and $V_{\frac{d}{2}+1}$ contains at least two vertices. Hence, we assume without loss of generality that $\left|V_{\frac{d}{2}-1}\right|\geq2$. Choose $w\in V_{\frac{d}{2}-1}$ and let

$ \begin{equation*} G^*=G-\left\{wx:x\in V_{\frac{d}{2}-2}\cup V_\frac{d}{2}\right\}+\left\{wy:y\in V_{\frac{d}{2}-1}\cup V_{\frac{d}{2}+1}\right\}, \end{equation*} $

then the vertex partition of $G^*$ is

$ V_0\cup V_1\cup \cdots\cup V_\frac{d-3}{2}\cup\left(V_{\frac{d}{2}-1}\backslash\{w\}\right)\cup\left(V_\frac{d}{2}\cup\{w\}\right)\cup V_{\frac{d}{2}+1}\cup\cdots \cup V_d $

and each of the two adjacent blocks of $V_{G^*}$ induces a complete bipartite graph. By direct calculation, we have

$ \begin{eqnarray*} S_k(G^*)-S_k(G) = \left[(|V_{\frac{d}{2}-1}|+|V_{\frac{d}{2}+1}|-1)+2^k|V_\frac{d}{2}|\right]-\\\left[2^k(|V_{\frac{d}{2}-1}|+|V_{\frac{d}{2}+1}|-1)+|V_\frac{d}{2}|\right] \\ = -(2^k-1)\left[|V_{\frac{d}{2}-1}|+|V_{\frac{d}{2}+1}|-(|V_\frac{d}{2}|+1)\right]\leq-(2^k-1)<0, \end{eqnarray*} $

a contradiction to the choice of $G$.

This completes the proof of Fact 2.

Now we come back to show the second part of Theorem 2.2. In view of Fact 2(i), if $d$ is odd, note that $|V_{\frac{d-1}{2}}|+|V_{\frac{d-1}{2}+1}|=n-d+1$, together with $\left||V_{\frac{d-1}{2}}|-|V_{\frac{d-1}{2}+1}|\right|\leq1$, we obtain that $G\cong G^*$, as desired.

In view of Fact 2(ii), if $d$ is even, note that $|V_{\frac{d}{2}}|+|V_{\frac{d}{2}-1}|+|V_{\frac{d}{2}+1}|=n-d+2$, together with $\left||V_{\frac{d}{2}}|-(|V_{\frac{d}{2}-1}|-|V_{\frac{d}{2}+1}|)\right|\leq1$, we obtain that $G\in \mathbb{B}$. Furthermore,

$ \mathbb{B}=\big\{\widehat{G}[p, q]:p+q=n-d+4, p=\frac{n-d+6}{2}\big\} $

for even $n$ and $\mathbb{B}=\big\{\widehat{G}[p, q]:p+q=n-d+4, p=\frac{n-d+7}{2}\big\}$ for odd $n$.

This completes the proof.