%0 Journal Article
%T Wiener Index of Graphs with Radius Two
%A Yin Chen
%A Baoyindureng Wu
%A Xinhui An
%J ISRN Combinatorics
%D 2013
%R 10.1155/2013/906756
%X The Wiener index of a graph is the sum of the distances between all pairs of vertices. It has been one of main descriptors that correlate a chemical compound's molecular graph with experimentally gathered data regarding the compound's characteristics. We characterize graphs with the maximum Wiener index among all graphs of order . with radius two. In addition, we pose a conjecture concerning the minimum Wiener index of graphs with given radius. If this conjecture is true, it will be able to answer an open question by You and Liu (2011). 1. Introduction Let be a connected graph. For two vertices , the distance between and in is the length of the shortest path connecting and in . The eccentricity of a vertex in is the largest distance from to another vertex of ; that is, . The diameter of is the maximum eccentricity in , denoted by . Similarly, the radius of is the minimum eccentricity in , denoted by . The Wiener index or total£¿ distance of , denoted by , is the sum of all distances between unordered pairs of distinct vertices of . In other words, The average distance of is defined as . A vertex is called a center of if . It is well known that every tree has either exactly one center or two adjacent centers. For the results on Wiener index of trees, we refer to Dobrynin et al. [1], and for some more results on Wiener index of graphs, one can see [2¨C12]. Plesn¨ªk [13] addresses a problem on distance of graphs, which remains unresolved. Problem 1. What is the maximum total or average distance among all graphs of order with diameter ? To see how hard to solve Problem 1, one just consider the following conjecture, due to DeLaVi£¿a and Waller [14]. Conjecture 1 (see [14]). Let G be a graph with diameter and order 2d + 1. Then , where denotes the cycle of length . For any connected graph , . By considering the close relationship between the diameter and the radius of a graph, it is natural to consider the following problem. Problem 2. What is the maximum total or average distance among all graphs of order with radius ? By Lemma 3 in Section 2, Problem 2 is more tractable than Problem 1; the graph with maximum total distance among all graphs of order with radius must be a tree. But, Problem 2 still seems to be quite challenging. The main focus of this paper is to tackle Problem 2 when the case . We will show that the graph with the maximum Wiener index among all connected graphs with radius two is a tree with somewhat fractal-like structure when the number of vertices of graphs goes to infinity. It provides some clues for the further investigation of Problem 2
%U http://www.hindawi.com/journals/isrn.combinatorics/2013/906756/