1 Introduction

The average distance is one of the most studied graph invariants in mathematics. Also Wiener index is the most famous topological indices in mathematical chemistry. In fact, the history of Wiener index goes back to 1947, when Wiener (1947) used the distances between atoms in the molecular graphs to calculate the boiling points of alkanes. This well-known research led to one of the most popular molecular structure-descriptors which is called Wiener index. In Harary (1959) many years after Wiener introduction, the same quantity has been studied and referred to by mathematicians as the gross status, the distance of graphs, average (mean) distance and the transmission. For finding more details in mathematical aspects of Wiener index, see recent survey (Knor et al. 2015). The Wiener index found numerous applications in pure mathematics and other sciences. For example in pure mathematics relation between Wiener index and eigenvalues of trees, independence number, distance matrix and more graph invariants are considered (Das and Nadjafi-Arani 2014; Khodashenas et al. 2011; Knor et al. 2015). Recently, we obtain a relation between Wiener index and several other popular topological indices of graph (Das et al. 2015). Moreover, using Wiener index in QSPR models in chemistry, crystallography, communication theory, facility location, etc., are some of these applications in other sciences, for more details see surveys (Bonchev 2002; Klavžar and Nadjafi-Arani 2015) and the references cited therein.

The computer programs Grafitti (Fajtlowicz and Waller 1987) and AutoGraphiX (Aouchiche et al. 2006) with the classical 1984 paper (Plesnik 1984) are three of the best sources for problems and conjectures related to average distance (as alias Wiener index) than other parameters of graphs. These sources designed some pretty and long-standing problems in this topic [see DeLaVina and Waller (2008) and Mukwembi and Vetrik (2014) and the references cited there in].

A problem that Plesnik addresses on Wiener index or average distance of graphs which remains unresolved for a long time is the following:

Problem 1

What is the maximum total (Wiener index) or average distance among all graphs of order n with diameter d?

To see how hard to solve Problem 1, consider the next Graffiti conjecture from DeLaVina and Waller (2008) that is a special case of Problem 1.

Conjecture 1 (DeLaVina and Waller 2008) Let G be a graph with diameter \(d>2\) and order \(2d + 1\). Then

$$\begin{aligned} W(G) \le W(C_{2d+1}), \end{aligned}$$

where \(C_{2d+1}\) denotes the cycle of length \(2d + 1\).

The next long-standing open problem that is so near to Problem 1 focus on radius of graphs.

Problem 2

What is the maximum total (Wiener index) or average distance among all graphs of order n with radius r?

Also these problems with some papers makes conjectures and theorems to approach in solution of Problems 1 and 2 [see DeLaVina and Waller (2008) and the references cited there in]. Recently, Su et al. (2015) studied some graph invariants very close to the Wiener index of graphs. Although, there are several papers for relation between toplogical indices and diameter (radius) of graphs but for the most well-known of them Wiener index is very less (see Wu et al. 2013). Recently, Chen et al. (2013) classified the maximum Wiener index of graphs with radius two. In Mukwembi and Vetrik (2014), by a very difficult proof, Mukwembi and Vetrik are presented some sharp bounds for trees of order n and diameter at most 6. Bounds stated as order n (O(n)) without any classification. Moreover, the trees with minimum Wiener index of order n and diameter d is presented in Liu and Pan (2008). Clearly, all the above recent papers worked on Wiener index and diameter in special class of graphs. These problems seem to be quite challenging because they defy all attempts to solve them for a long time.

The paper is organized as follows. In Sect. 2, we state some preliminary definitions and lemmas. In Sect. 3, we give an upper bound on the Wiener index (and average distance) in terms of order and radius of trees and graphs, and characterize the extremal graphs. Moreover, we obtain an upper bound on the average distance of graphs in terms of order and independence number of G. In Sect. 4, we present an upper bound on the Wiener index (and average distance) in terms of order, radius and maximum degree of trees and graphs, and also characterize the extremal graphs.

2 Preliminary

Let G be an \((n,\,m)\)-connected graph with vertex set V(G) and edge set E(G), where \(|V(G)|=n\) and \(|E(G)|=m\). For a graph G, we let \(d_{G}(v)\) be the degree of a vertex v in G. The maximum vertex degree in G is denoted by \(\Delta \) . The distance between two vertices u and v in G, namely, the length of the shortest path between u and v is denoted by \(d_{G}(u,\,v)\). The eccentricity of a vertex v in a graph G is defined to be \(ec_{G}(v)=\max \{d_{G}(v,\,u)\,|\,u\in V(G)\}\). The radius of a graph is the minimum graph eccentricity of any graph vertex in a graph. The radius of a graph G , is denoted by r(G). Thus we have

$$\begin{aligned} r(G)=\min \{ec_{G}(v_i):\,v_i\in V(G)\}. \end{aligned}$$

The Wiener index of a graph G equals

$$\begin{aligned} W(G)=\frac{1}{2}\,\sum \limits _{u\in V(G)}\,\sum \limits _{v\in V(G)}\,d_G(u,\,v) \end{aligned}$$

and the average distance \(\mu (G)\) of G equals

$$\begin{aligned} \mu (G)=\frac{2}{n\,(n-1)}\,W(G)\,. \end{aligned}$$

For recent results, the reader is referred to Klavžar and Nadjafi-Arani (2014a, b) and for review, see Dobrynin et al. (2001) and Klavžar (2013).

Let F be a forest with k connected components \((k\ge 1)\), each being a tree. Suppose that \(F=T_1\cup T_2\cup \cdots \cup T_k\) , where \(T_i\) \((1\le i \le k)\) is a tree of F. Denote by \(N_2(F)\) the sum over all pairs of components, of the product of the number of vertices of two components of F, that is,

$$\begin{aligned} N_2(F)=\sum \limits _{1\le i<j\le k}\,n(T_i)\,n(T_j)\,, \end{aligned}$$

where \(n(T_i)\) is the number of vertices in tree \(T_i\) . The following result is obtained from Škrekovski and Gutman (2014) and Wiener (1947):

Lemma 2.1

Let T be a tree on n vertices. Then

$$\begin{aligned} W(T)=\sum \limits _{e\in E(T)}\,N_2(T-e)\,. \end{aligned}$$
(1)

For a subset Z of V(G), let \(G\backslash Z\) be the subgraph of G obtained by deleting the vertices of Z together with the incident edges. Given a graph G, a subset S of V(G) is said to be an independent set of G if the subgraph G[S], induced by S, is a graph with |S| isolated vertices. The independence number \(\alpha (G)\) of G is the number of vertices in the largest independent set of G. As usual, \(K_{1,\,n-1}\) is the star of n vertices. Other notation and terminology not defined here will conform to those in Bondy and Murty (1976).

3 Maximum Wiener index in terms of n and r

We now give an upper bound on W(T) in terms of n, r and characterize the extremal graphs.

Theorem 3.1

Let T be a tree of order \(n\,(>1)\) with radius r. Then

$$\begin{aligned} W(T)\le r(n-r)\left[ n-r+\frac{r(r-1)}{n-1}\right] \end{aligned}$$
(2)

with equality holding in (2) if and only if \(T\cong K_{1,\,n-1}\) .

Proof

For \(r=1\), \(T\cong K_{1,\,n-1}\) . We have \(W(T)=(n-1)^2\) and hence the equality holds in (2). Otherwise, \(r\ge 2\). Since r is the radius of tree T, then there exists a vertex v such that \(r=\max _{u\in V(T)}\,d_T(v,\,u)\) . Suppose that v is a root of the tree T. Let \(N_i(v)\) \((0\le i \le r)\) be the set of vertices at distance i from vertex v, that is,

$$\begin{aligned} N_i(v)=\left\{ u\in V(T):\,d_T(v,\,u)=i\right\} . \end{aligned}$$

Then we have

$$\begin{aligned} V(G)=N_0(v)\cup N_1(v)\cup N_2(v)\cup \cdots \cup N_r(v)~~~ \text{ and } ~~N_i(v)\cap N_j(v)=\emptyset ,~~i\ne j. \end{aligned}$$

Let \(|N_i(v)|=n_i\) \((1\le i \le r)\) and \(n_0=1\). One can easily see that

$$\begin{aligned} n_0+n_1+n_2+\cdots +n_r=n. \end{aligned}$$

Set

$$\begin{aligned} S_i=n_0+n_1+n_2+\cdots +n_i\,,~~0\le i\le r,\,\,\, \text{ and } \,\,\,S_r=n. \end{aligned}$$

Let \(M_i(v)\) \((1\le i \le r)\) be the set of edges at distance \(i-1\) from vertex v, that is,

$$\begin{aligned} M_i(v)=\left\{ e=uw\in E(T):u\in N_{i-1}(v),\,w\in N_i(v)\right\} ~~ \text{ and } ~~|M_i(v)|=n_i. \end{aligned}$$

Then we have

$$\begin{aligned} E(T)=M_1(v)\cup M_2(v)\cup \cdots \cup M_r(v)~~~~ \text{ and } ~~M_i(v)\cap M_j(v)=\emptyset ,~~i\ne j. \end{aligned}$$

Let \(T_i\) be a subtree of tree T such that \(v\in V(T_i)\) and \(V(T_i)=\{u\!\in \! V(T)\,|\,d_T(v,\,u)\!\le \! i\}\). Then \(|V(T_i)|=1+n_1+n_2+\cdots +n_i=S_i\) . Let \(t_j^i\) \((1 \le j \le n_i)\) be the number of vertices in the j-th connected component in \(T\backslash V(T_{i-1})\). Thus we have

$$\begin{aligned} t_1^i+\cdots +t_{n_i}^i =n-S_{i-1}\,. \end{aligned}$$

Using the above result, we have

$$\begin{aligned} \sum \limits _{e\in M_i(v)}\,N_2(T-e)= & {} \sum \limits ^{n_i}_{j=1}\,t^i_{j}\,(n-t^i_{j}) \nonumber \\= & {} \sum \limits ^{n_i}_{j=1}\,t^i_{j}\,(S_{i-1}+t^i_{1}+t^i_{2}+ \cdots +t^i_{j-1}+t^i_{j+1}+\cdots +t^i_{n_i})\nonumber \\= & {} S_{i-1}\,\sum \limits ^{n_i}_{j=1}\,t^i_{j}+2 \sum \limits _{1\le j<k\le n_i}t_j^i\,t_k^i\nonumber \\= & {} S_{i-1}\,(n-S_{i-1})+2 \sum \limits _{1\le j<k\le n_i} t_j^i\,t_k^i~~~ \text{ for } ~i=1,\,2,\ldots ,\,r.\nonumber \\ \end{aligned}$$
(3)

By Cauchy-Schwarz inequality, we have

$$\begin{aligned} \left( \sum \limits ^{n_i}_{j=1}t_j^i\right) ^2\le n_i\,\sum \limits ^{n_i}_{j=1}\left( t_j^i\right) ^2 \end{aligned}$$
(4)

with equality holding if and only if \(t_1^i=t_2^i=\cdots =t_{n_i}^i\) . Since

$$\begin{aligned} \left( \sum \limits ^{n_i}_{j=1}t_j^i\right) ^2= \sum \limits ^{n_i}_{j=1}\left( t_j^i\right) ^2+2\sum \limits _{1\le j<k\le n_i}t^i_j\,t^i_k, \end{aligned}$$

using (4), we have

$$\begin{aligned} \sum \limits _{1\le j<k\le n_i}t^i_j\,t^i_k\le \frac{n_i-1}{2\,n_i}\,\left( \sum \limits ^{n_i}_{j=1}\,t^i_j\right) ^2 =\frac{n_i-1}{2\,n_i}\,\left( n-S_{i-1}\right) ^2 \end{aligned}$$

with equality holding if and only if \(t_1^i=t_2^i=\cdots =t_{n_i}^i\) .

Using the above result in (3), for \(i=1,\,2,\ldots ,\,r\), we get

$$\begin{aligned} \sum \limits _{e\in M_i(v)}\,N_2(T-e)\le S_{i-1}\,(n-S_{i-1})+\frac{n_i-1}{n_i}\,\left( n-S_{i-1}\right) ^2 \end{aligned}$$
(5)

with equality holding if and only if \(t_1^i=t_2^i=\cdots =t_{n_i}^i\) .

Using (5) in (1), we have

$$\begin{aligned} W(G)= & {} \sum \limits _{e\in M_1(v)}\,N_2(T-e)+\sum \limits _{e\in M_2(v)}\,N_2(T-e)+\cdots +\sum \limits _{e\in M_r(v)}\,N_2(T-e)\nonumber \\\le & {} \sum \limits _{j=1}^{r}\left[ S_{j-1}(n-S_{j-1})+ \frac{n_j-1}{n_j}\left( n-S_{j-1}\right) ^2\right] . \end{aligned}$$
(6)

with equality holding if and only if \(t_1^i=t_2^i=\cdots =t_{n_i}^i\) \((1\le i\le r)\).

Now we define

that is,

$$\begin{aligned} P_i=\sum \limits ^r_{j=i}\,n_j\,,~~~~~~1\le i\le r. \end{aligned}$$

Then we have

$$\begin{aligned} S_{i-1}+P_i=\sum \limits ^{i-1}_{j=0}\,n_j+ \sum \limits ^r_{j=i}\,n_j=\sum \limits ^r_{j=0}\,n_j=n, \end{aligned}$$

that is,

$$\begin{aligned} P_i=n-S_{i-1}\,. \end{aligned}$$
(7)

Using the weighted arithmetic-harmonic mean, we get

$$\begin{aligned} \frac{\sum \limits ^r_{k=1}\,P_k\cdot \displaystyle {\frac{P_k}{n_k}}}{\sum \limits ^r_{k=1}\,P_k}\ge \frac{\sum \limits ^r_{k=1}\,P_k}{\sum \limits ^r_{k=1}\,n_k}\,, \end{aligned}$$

that is,

$$\begin{aligned} \sum \limits ^r_{k=1}\,\frac{P^2_k}{n_k}\ge \frac{\Big (\sum \limits ^r_{k=1}\,P_k\Big )^2}{n-1} \end{aligned}$$
(8)

with equality holding if and only if

$$\begin{aligned} \frac{P_1}{n_1}=\frac{P_2}{n_2}=\cdots =\frac{P_{r}}{n_r}\,. \end{aligned}$$

Now,

$$\begin{aligned} \sum \limits ^r_{k=1}\,P_k= & {} n_1+2n_2+3n_3+\cdots +(r-1)n_{r-1}+r\,n_r\nonumber \\= & {} r(n_1+n_2+\cdots +n_r)-\Big [(r-1)n_1+(r-2)n_2+\cdots +2n_{r-2}+n_{r-1}\Big ]\nonumber \\\le & {} r(n-1)-2\Big [(r-1)+(r-2)+\cdots +2+1\Big ]\nonumber \\= & {} r(n-1)-r(r-1)=r(n-r). \end{aligned}$$
(9)

Using (7) and (8) in (6), we get

$$\begin{aligned} W(T)\le & {} \sum ^r_{k=1}\,\left[ n\,P_k-\frac{P^2_k}{n_k}\right] \\\le & {} n\,\sum ^r_{k=1}\,P_k-\frac{\Big (\sum \limits ^r_{k=1}\,P_k\Big )^2}{n-1}. \end{aligned}$$

Since \(f(x)=n\,x-\displaystyle {\frac{x^2}{n-1}}\) is an increasing function on \(1\le x\le \displaystyle {\frac{n(n-1)}{2}}\) and hence

$$\begin{aligned} W(T)\le f\left( \sum ^r_{k=1}\,P_k\right) \le f\left( r(n-r)\right) =nr(n-r)-\displaystyle {\frac{r^2\,(n-r)^2}{n-1}}\,, \end{aligned}$$

which gives the required result in (2).

Now we have to prove that the inequality in (2) is strict for \(r\ge 2\). By contradiction, we will show this result. For this, we assume that all the inequalities in the above must be equalities. From the equality in (6), we get

$$\begin{aligned} t_1^k=t_2^k=\cdots =t_{n_k}^k\,,~~~~~~1\le k\le r. \end{aligned}$$

From the equality in (8), we get

$$\begin{aligned} \frac{P_1}{n_1}=\frac{P_2}{n_2}=\cdots =\frac{P_{r}}{n_r}\,. \end{aligned}$$
(10)

From the equality in (9), we get

$$\begin{aligned} n_1=n_2=\cdots =n_{r-1}=2. \end{aligned}$$
(11)

Using the above result in (10), we get \(P_1=P_2=\cdots =P_{r-1}\) . For \(r>2\), we have \(P_1>P_2>\cdots >P_r\), a contradiction. Therefore we must have \(r=2\) and hence \(n_1=2\), by (11). Since \(r=2\), we have \(P_2=n_2\). From (10), we get \(P_1=n_1<n_1+n_2=P_1\), a contradiction. This completes the proof. \(\square \)

Theorem 3.2

Let G be a connected graph of order \(n\,(>1)\) with radius r. Then

$$\begin{aligned} W(G)\le r(n-r)\left[ n-r+\frac{r(r-1)}{n-1}\right] \end{aligned}$$
(12)

with equality holding in (12) if and only if \(G\cong K_{1,\,n-1}\) .

Proof

Since G is a connected graph with radius r, then there exists a spanning tree T of G such that \(r(G)=r(T)\) and \(W(G)\le W(T)\). Moreover, we have \(W(G)<W(G-e)\), where e is any edge in G. By Theorem 3.1, we get the required result in (12). Moreover, the equality holds in (12) if and only if \(T\cong K_{1,\,n-1}\) . \(\square \)

Corollary 3.3

Let G be a connected graph of order \(n\,(>1)\) with radius r. Then

$$\begin{aligned} \mu (G)\le \frac{2\,r(n-r)}{n\,(n-1)}\left[ n-r+\frac{r(r-1)}{n-1}\right] \end{aligned}$$
(13)

with equality holding if and only if \(G\cong K_{1,\,n-1}\) .

We now give an upper bound on \(\mu (G)\) in terms of n and \(\alpha \).

Theorem 3.4

Let G be a connected graph of order \(n(>\!1)\) with independence number \(\alpha \). Then

$$\begin{aligned}&\mu (G)\le {\left\{ \begin{array}{ll} \displaystyle {\frac{2\alpha (n-\alpha )}{n(n-1)}\left[ n-\alpha + \frac{\alpha (\alpha -1)}{n-1}\right] } &{} \text {if}\, \alpha \le \displaystyle {\frac{n}{2}}, \\ \displaystyle { \frac{3n}{8}}+\frac{9}{32} &{}\, \text {if} \alpha > \displaystyle {\frac{n}{2}} \end{array}\right. } \end{aligned}$$
(14)

with equality holding if and only if \(G\cong K_2\).

Proof

One can easily see that the equality holds in (14) for \(K_2\). Otherwise, \(n\ge 3\). Let us consider a function

$$\begin{aligned} g(x)=nx(n-x)-\frac{x^2(n-x)^2}{n-1}\,,~~~~1\le x\le n\,. \end{aligned}$$

Then we have

$$\begin{aligned} g^{\prime }(x)=(n-2x)\left[ n-\frac{2}{n-1}\,x(n-x)\right] . \end{aligned}$$

Thus g(x) is an increasing function on \(1\le x\le \displaystyle {\frac{n}{2}}\) and a decreasing function on \(\displaystyle {\frac{n}{2}}\le x\le n\) . For G, we have \(r\le \alpha \). If \(r\le \alpha \le \displaystyle {\frac{n}{2}}\) , then from (13), we get

$$\begin{aligned} \mu (G)\le \displaystyle {\frac{2\alpha (n-\alpha )}{n(n-1)} \left[ n-\alpha +\frac{\alpha (\alpha -1)}{n-1}\right] }\,. \end{aligned}$$

Otherwise, \(\alpha >\displaystyle {\frac{n}{2}}\) . But we have

$$\begin{aligned} g(x)\le g\left( \displaystyle {\frac{n}{2}}\right) \,. \end{aligned}$$

By simple calculation, one can easily see that

$$\begin{aligned} \mu (G)\le \displaystyle {\frac{2}{n(n-1)}}\,g\left( \displaystyle {\frac{n}{2}}\right) \le \frac{3n}{8}+\frac{9}{32}\,. \end{aligned}$$

The first part of the proof is done.

The equality holds in (14) if and only if \(G\cong K_{1,\,n-1}\) with \(r=\alpha \) when \(\alpha \le \displaystyle {\frac{n}{2}}\) and \(r=\frac{n}{2}\) when \(\alpha > \displaystyle {\frac{n}{2}}\) (by Corollary 3.3), a contradiction. This completes the proof. \(\square \)

4 Maximum Wiener index (or average distance) in terms of n, r and \(\Delta \)

In this section we are interested to find graphs which maximize the Wiener index in terms of the number of vertices n, radius r and maximum degree \(\Delta \). In fact, Fischermann et al. (2003) have also determined the trees which maximize the Wiener index, but in a much more restricted family of trees which have two distinct vertex degrees only. Wang (2008) characterize the trees that achieve the maximum and minimum Wiener index, given the number of vertices n and the degree sequence. Stevanović (2008) obtained the trees which maximize the Wiener index among all graphs of order n and maximum degree \(\Delta \). Now, we look this problem from another aspect. For this, consider a tree \(T_{n,\,r,\,\Delta }\) is defined as follows. Start with the root having \(\Delta \) children. Every vertex different from the root, which is not in the last level (that is, r-th level), has exactly \(\Delta -1\) children. We now give another upper bound on W(T) in terms of n, r and \(\Delta \).

Theorem 4.1

Let T be a tree of order n with radius r and maximum degree \(\Delta \ge 3\). Then

$$\begin{aligned} W(T)\le n-1 +\frac{\Delta \,(\Delta -1)}{(\Delta -2)^3}&\Bigg [(\Delta -1)^{2r-1}(r\Delta ^2-2r\Delta -2\Delta +1) \nonumber \\&\quad -(\Delta -1)^{r-1}(\Delta ^2-6\Delta +4) + \Delta -3\Bigg ]\qquad \end{aligned}$$
(15)

with equality holding in (15) if and only if \(T\cong T_{n,\,r,\,\Delta }\) .

Proof

Here we use the same notation as in the proof of Theorem 3.1. Let \(a=\Delta -1\). One can easily see that

$$\begin{aligned} n_i\le \Delta \,a^{i-1}\,\,\,\, \text{ and } \,\,\,n_{i+k}\le n_i\,a^k\,,\,\,\,i\ge 1,\,k\ge 1. \end{aligned}$$
(16)

Using the above result with \(\Delta \ge 3\), we get

$$\begin{aligned} S_i= & {} 1+n_1+n_2+\cdots +n_i\le 1+\sum ^i_{j=1}\Delta \,a^{j-1}=1+\frac{a^i-1}{a-1}\,\Delta \end{aligned}$$
(17)

and

$$\begin{aligned} n-S_i= & {} n_{i+1}+n_{i+2}+\cdots +n_{r}\le \sum \limits ^r_{j=i+1}\Delta \,a^{j-1}=\frac{a^r-a^i}{a-1}\,\Delta . \end{aligned}$$
(18)

Again, by (16), we get

$$\begin{aligned} \frac{n-S_{i-1}}{n_i}= & {} \frac{n_{i}+n_{i+1}+\cdots +n_{r}}{n_i} \le 1+a+a^2+\cdots +a^{r-i}=\frac{a^{r-i+1}-1}{a-1}.\nonumber \\ \end{aligned}$$
(19)

Using (16), (17), (18) and (19), we get

$$\begin{aligned}&\sum \limits _{i=1}^{r-1}\left[ S_i(n-S_i)+\frac{n_i-1}{n_i} \left( n-S_{i-1}\right) ^2\right] \\\le & {} \Delta \,\sum \limits ^{r-1}_{i=1}\, \left[ \frac{\left( \Delta \,a^i-2\right) \left( a^r-a^i\right) }{(a-1)^2}+\frac{\left( \Delta \,a^{i-1}-1\right) \left( a^r-a^{i-1}\right) \left( a^{r-i+1}-1\right) }{(a-1)^2}\right] \\&\quad \text{ as } a=\Delta -1\\= & {} \frac{\Delta }{(a-1)^2}\,\sum \limits ^{r-1}_{i=1}\, \Big [\Delta \,a^{2r}+\Delta \,a^r(a-2)\,a^{i-1}- a^{2r-i+1}-\Delta (a^2-1)\,a^{2i-2}\\&\quad +\,(2a-1)\,a^{i-1}\Big ]\\= & {} \frac{\Delta }{(a-1)^2}\,\Bigg [\Delta (r-1)\,a^{2r} +\,\Delta a^r(a-2)\times \frac{a^{r-1}-1}{a-1}-a^{r+2} \times \frac{a^{r-1}-1}{a-1}\\&\quad -\Delta (a^{2r-2}-1)\\&\quad +\,(2a-1)\times \frac{a^{r-1}-1}{a-1}\Bigg ]\\= & {} \frac{\Delta }{(a-1)^3}\,\Bigg [\Delta (a-1) \Big ((r-1)a^{2r}-a^{2r-2}+1\Big )\\&\quad -\,(a^{r-1}-1) \Big ((\Delta +1)a^r-2\Delta +3\Big )\Bigg ]\,. \end{aligned}$$

Using the above result with (16), from (6), we get

$$\begin{aligned} W(T)\le & {} \sum \limits _{i=1}^{r-1}\left[ S_{i}(n-S_{i})+ \frac{n_i-1}{n_i}\left( n-S_{i-1}\right) ^2\right] +(n-1)+n_r\,(n_r-1)\nonumber \\\le & {} n-1+\Delta \,a^{r-1}\Big (\Delta \,a^{r-1}-1\Big )\nonumber \\&+\,\frac{\Delta }{(a-1)^3}\,\Bigg [\Delta (a-1) \Big ((r-1)a^{2r}-a^{2r-2}+1\Big )-(a^{r-1}-1)\nonumber \\&\quad \Big ((\Delta +1) a^r-2\Delta +3\Big )\Bigg ]\,, \end{aligned}$$
(20)

where \(a=\Delta -1\). Therefore, we have:

$$\begin{aligned} W(T)\le & {} n-1+\Delta \,(\Delta -1)^{r-1}\Big (\Delta \,(\Delta -1)^{r-1}-1\Big ) +\frac{\Delta }{(\Delta -2)^3}\,\\&\quad \times \Bigg [\Delta (\Delta -2)\Big ((r-1)(\Delta -1)^{2r} -(\Delta -1)^{2r-2}+1\Big ) \\&\quad -\Big ((\Delta -1)^{r-1}-1\Big )\Big ((\Delta +1)(\Delta -1)^r-2\Delta +3\Big )\Bigg ]. \end{aligned}$$

By a simple calculation of above expression, we get the required result in (15). The first part of the proof is done.

The equality holds in (20) if and only if \(t_1^i=t_2^i=\cdots =t_{n_i}^i\), \(1\le i\le r\) (by Theorem 3.1). Moreover, the equality holds in (16) if and only if

$$\begin{aligned} n_i=\Delta \,(\Delta -1)^{i-1}\,,\,i=1,\,2,\ldots ,\,r. \end{aligned}$$

Hence the equality holds in (15) if and only if

$$\begin{aligned} t_1^i=t_2^i=\cdots =t_{n_i}^i~~(1\le i\le r),~~ \text{ and } ~n_i=\Delta \,(\Delta -1)^{i-1}\,,\,i=1,\,2,\ldots ,\,r, \end{aligned}$$

that is,

$$\begin{aligned} d_T(v_i)=\Delta ,~~v_i\in V(T)\backslash N_r(v)~~ \text{ and } ~~d_T(v_i)=1,~~v_i\in N_r(v), \end{aligned}$$

that is,

$$\begin{aligned} T\cong T_{n,\,r,\,\Delta }\,. \end{aligned}$$

This completes the proof of the theorem. \(\square \)

Corollary 4.2

Let T be a tree of order \(n\,(>1)\) with radius r and maximum degree \(\Delta \ge 3\). Then

$$\begin{aligned}&\mu (T)\le \frac{2}{n} +\frac{2\Delta \,(\Delta -1)}{n(n-1)(\Delta -2)^3}\Bigg [(\Delta -1)^{2r-1} (r\Delta ^2-2r\Delta -2\Delta +1) \\&\quad -(\Delta -1)^{r-1}(\Delta ^2-6\Delta +4) + \Delta -3\Bigg ] \end{aligned}$$

with equality holding if and only if \(T\cong T_{n,\,r,\,\Delta }\) .

The center of a graph is the set of vertices with eccentricity equal to the radius r. Let C(G) be the center of a graph G. We now give an upper bound on W(G) in terms of n, r, \(\Delta \), and characterize the extremal graphs.

Theorem 4.3

Let G be a graph of order n with radius r and maximum degree vertex v of degree \(\Delta \ge 3\). If \(v\in C(G)\), then

$$\begin{aligned}&W(G)\le n-1 +\frac{\Delta \,(\Delta -1)}{(\Delta -2)^3} \Bigg [(\Delta -1)^{2r-1}(r\Delta ^2-2r\Delta -2\Delta +1) \\&\quad - (\Delta -1)^{r-1}(\Delta ^2-6\Delta +4) + \Delta -3\Bigg ]. \end{aligned}$$

Proof

Consider the graph G as a v rooted graph with \(d_G(v)=\Delta \) and define the vertices of level i are as follows:

$$\begin{aligned} N_i(v)=\left\{ u\in V(G):\,d_G(v,\,u)=i\right\} . \end{aligned}$$

Suppose that \(G^{\prime }\) obtain from G by deleting the edges between vertices of \(N_i\) (for each i). Indeed \(G^{\prime }\) is a spanning bipartite subgraph of G. We now obtain a spanning tree T from \(G^{\prime }\) by deleting some edges between \(N_{i-1}(v)\) and \(N_{i}(v)\) (\(i\ge 2\)). Clearly, the based on deleting edges, the vertex v is of degree \(\Delta \) and T is a spanning tree of G with maximum degree \(\Delta \) and radius r. From this fact \(W(G) \le W(T)\) and applying Theorem 4.1, we get the required result. \(\square \)

5 Conclusion and future work

In this paper, we obtained an upper bound on Wiener index of trees and graphs in terms of number of vertices, radius, and characterize the extremal graphs. Besides these, we presented an upper bound on average distance in terms of order and independence number of graph G. Finally we gave another upper bound on Wiener index of graphs in terms of number of vertices, radius and maximum degree, and characterize the extremal graphs. These results are not enough to solve Problems 1 and 2, and Conjecture 1. We believe that Conjecture 1 is one of the best challenge open problem for distance-based topological indices of graphs. Still Problems 1 and 2, and Conjecture 1 are far from the solution.