Abstract
Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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
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
The Wiener index of a graph G equals
and the average distance \(\mu (G)\) of G equals
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,
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
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
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,
Then we have
Let \(|N_i(v)|=n_i\) \((1\le i \le r)\) and \(n_0=1\). One can easily see that
Set
Let \(M_i(v)\) \((1\le i \le r)\) be the set of edges at distance \(i-1\) from vertex v, that is,
Then we have
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
Using the above result, we have
By Cauchy-Schwarz inequality, we have
with equality holding if and only if \(t_1^i=t_2^i=\cdots =t_{n_i}^i\) . Since
using (4), we have
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
with equality holding if and only if \(t_1^i=t_2^i=\cdots =t_{n_i}^i\) .
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,
Then we have
that is,
Using the weighted arithmetic-harmonic mean, we get
that is,
with equality holding if and only if
Now,
Using (7) and (8) in (6), we get
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
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
From the equality in (8), we get
From the equality in (9), we get
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
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
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
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
Then we have
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
Otherwise, \(\alpha >\displaystyle {\frac{n}{2}}\) . But we have
By simple calculation, one can easily see that
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
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
Using the above result with \(\Delta \ge 3\), we get
and
Again, by (16), we get
Using (16), (17), (18) and (19), we get
Using the above result with (16), from (6), we get
where \(a=\Delta -1\). Therefore, we have:
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
Hence the equality holds in (15) if and only if
that is,
that is,
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
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
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:
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.
References
Aouchiche M, Bonnefoy JM, Fidahoussen A, Caporossi G, Hansen P, Hiesse L, Lachere J, Monhait A (2006) Variable neighborhood search for extremal graphs. 14. The autoGraphiX 2 system. In: Liberti L, Maculan N (eds) Global Optimization: from theory to implementation. Springer, New York, pp 281–310
Bonchev D (2002) The Wiener number-some applications and new developments. In: Rouvray DH, King RB (eds) Topology in chemistry: discrete mathematics of molecules. Horwood, Chichester, pp 58–88
Bondy JA, Murty USR (1976) Graph theory with applications. Macmillan, New York
Chen Y, Wu B, An X (2013) Wiener index of graphs with radius two. ISRN Combinatorics. doi:10.1155/2013/906756
Das KC, Nadjafi-Arani MJ (2014) Comparison between the Szeged index and the eccentric connectivity index. Discrete Appl Math 186:74–86
Das KC, Gutman I, Nadjafi-Arani MJ (2015) Relations between distance-based and degree-based topological indices. Appl Math Comput 270:142–147
DeLaVina E, Waller B (2008) Spanning trees with many leaves and average distance. Electron J Combin 15(R33):16
Dobrynin AA, Entringer R, Gutman I (2001) Wiener index of trees: theory and applications. Acta Appl Math 66:211–249
Fajtlowicz S, Waller WA (1987) On two conjectures of GRAFFITI II. Congr Numer 60:187–197
Fischermann M, Hoffmann A, Rautenbach D, Székely L, Volkmann L (2003) Wiener index versus maximum degree in trees. Discrete Appl Math 122:127–137
Harary F (1959) Status and contrastatus. Sociometry 22(1):23–43
Khodashenas H, Nadjafi-Arani MJ, Ashrafi AR, Gutman I (2011) A new proof of the Szeged–Wiener theorem. Kragujev J Math 35(1):165–172
Klavžar S (2013) Structure of Fibonacci cubes: a survey. J Comb Optim 25:505–522
Klavžar S, Nadjafi-Arani MJ (2015) Cut method: update on recent developments and equivalence of independent approaches. Curr Org Chem 19(4):348–358
Klavžar S, Nadjafi-Arani MJ (2014) Wiener index in weighted graphs via unification of \(\Theta ^{\ast }\)-classes. Eur J Combin 36:71–76
Klavžar S, Nadjafi-Arani MJ (2014) Improved bounds on the difference between the Szeged index and the Wiener index of graphs. Eur J Combin 39:148–156
Knor M, Škrekovski R, Tepeh A (2015) Mathematical aspects of Wiener index. arXiv:1510.00800
Liu H, Pan XF (2008) On the Wiener index of trees with fixed diameter. MATCH Commun Math Comput Chem 60:85–94
Mukwembi S, Vetrik T (2014) Wiener index of trees of given order and diameter at most 6. Bull Aust Math Soc 89:379–396
Plesnik J (1984) On the sum of all distances in graph or diagraph. J Graph Theory 8:1–24
Škrekovski R, Gutman I (2014) Vertex version of the Wiener theorem. MATCH Commun Math Comput Chem 72:295–300
Stevanović D (2008) Maximizing Wiener index of graphs with fixed maximum degree. MATCH Commun Math Comput Chem 60:71–83
Su G, Xiong L, Su X, Chen X (2015) Some results on the reciprocal sum-degree distance of graphs. J Comb Optim 30:435. doi:10.1007/s10878-013-9645-5
Wang H (2008) The extremal values of the Wiener index of a tree with given vertex degree sequence. Discrete Appl Math 156:2647–2656
Wiener H (1947) Structural determination of paraffin boiling points. J Am Chem Soc 69:17–20
Wu B, An X, Liu G, Yan G, Liu X (2013) Minimum degree, edge-connectivity and radius. J Comb Optim 26(3):585–591
Acknowledgments
The authors are much grateful to the anonymous referee for his/her valuable comments on our paper, which have considerably improved the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Das, K.C., Nadjafi-Arani, M.J. On maximum Wiener index of trees and graphs with given radius. J Comb Optim 34, 574–587 (2017). https://doi.org/10.1007/s10878-016-0092-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0092-y