In the present paper we investigate the relationship between Wiener number W, hyper-Wiener number R, Wiener vectors WV, hyper-Wiener vectors HWV, Wiener polynomial H, hyper-Wiener polynomial HH and distance distribution DD of a (molecular) graph. It is shown that for connected graphs G and G*, the following five statements are equivalent:
; and if G and G* have same distance distribution DD then they have same W and R but the contrary is not true. Therefore, we further investigate the graphs with same distance distribution. Some construction methods for finding graphs with same distance distribution are given.
The Wiener index is one of the oldest topological indices of molecular structures. It was put forward by the physico-chemist Harold Wiener  in 1947. The Wiener index of a connected graph is defined as the sum of distances between all pairs of vertices in :
where is the vertex set of , and is the distance between vertices and in .
As an extension of the Wiener index of a tree, Randić  introduced Wiener matrix and hyper-Wiener index of a tree. For any two vertices in , let denote the unique path in with end vertices and the length , let and denote the components of containing and , respectively, and let and denote the numbers of the vertices in and , respectively. Then the Wiener matrix and the hyper-Wiener number of can be given by , , and .
In Refs.   , Randic and Guo and colleagues further introduced the higher Wiener numbers and some other Wiener matrix invariants of a tree . The higher Wiener numbers can be represented by a Wiener number sequence , where . It is not difficult to see , and .
After the hyper-Wiener index of a tree was introduced, many publications  -  have appeared on calculation and generalization of the hyper-Wiener index. Klein et al.  generalized the hyper-Wiener index so as to be applicable to any connected structure. Their formula for the hyper-Wiener index of a graph is
The relation between Hyper-Wiener and Wiener index was given by Gutman  .
The Hosoya polynomial of a connected graph was introduced by Hosoya  in 1988, which he named as the Wiener polynomial of a graph:
where is the number of pairs of vertices in the graph that are distance apart.
In Ref.  , Cash introduced a new hyper-Hosoya polynomial
The relationship between the Hosoya polynomial and the Hyper-Hosoya polynomial was discussed  .
The sequence is also known (since 1981) as the dis- tance distribution of a graph  , denoted by . It is easy to see that .
Later the definition of higher Wiener numbers is extended to be applicable to any connected structure by Guo et al.  . For a connected graph with n vertices, denoted by , let where is the distance between vertices and . Then , , are called the higher Wiener numbers of . The vector is called the hyper-Wiener vector of , denoted by . The concept of the Wiener vector of a graph is also introduced in ref.  . For a connected graph with vertices, denoted by , let , . The vector is called the Wiener vector of , denoted by .
Moreover, a matrix sequence , called the Wiener matrix sequence, and their sum , called the hyper-Wiener matrix, are introduced, where is the distance matrix. A Wiener polynomial sequence and a weighted hyper Wiener polynomial of a graph are also in- troduced.
In this paper, based on the results in ref.  , we study the relation between Wiener number , hyper-Wiener number , Wiener vector , hyper- Wiener vector , Hosoya polynomial , hyper-Hosoya polynomial and distance distribution of a graph. It is shown that for connected graphs and , the the contrary is not true. This means that the distance dis- tribution of a graph is an important topological index of molecular graphs. Therefore, we further investigate the graphs with same distance distribution. It is shown that the graphs with same vertex number, edge number, and diameter 2 have same distance distribution. Some construction methods for finding graphs with same distance distribution are given.
2. The Relation between
Let denote the diameter of a graph .
Theorem 2.1. Let and be connected graphs. Then the following five statements are equivalent:
1) and have same distance distribution ;
2) and have same Wiener vector ;
3) and have same hyper-Wiener vector ;
4) and have same Wiener polynomial ;
5) and have same hyper-Wiener polynomial .
Proof. We shall show the equivalent statements by (1)Þ(2)Þ(3)Þ(4)Þ(5)Þ(1).
(1)Þ(2). By the definitions of and ,
Clearly, if , then .
(2)Þ(3). If , then for . So for . Hence .
(3)Þ(4). Suppose . Then for , and .
If , then
Assume, for , . Let . Then
By induction hypothesis,
. So we have
Now it follows that for , and so
(4)Þ(5). By the definitions of Hosoya polynomial and hyper-Hosoya polynomial , it is easy to see that, if , then .
(5)Þ(1). If , then for . Therefore . □
Theorem 2.2. Let and be two graphs with same distance dis- tribution. Then and have same and .
Proof: By the definitions of , and ,
Clearly, if , then and . ,
However, the contrary of the theorem doesn’t hold. For instance, the trees and (resp. and ) in Figure 1 have same and , but they have different distance distributions.
3. Graphs with Same Distance Distribution
From the above theorems, one can see that, if two graphs and have
Figure 1. , , , . , , , .
same distance distribution , then they have same and . So it is significant to study the graphs with same distance dis- tribution.
1) The minimum non-isomorphic acyclic graphs with same DD
By direct calculation, we know the minimum non-isomorphic acyclic graphs with same distance distribution are the following two pairs of trees in Figure 2 which have 9 vertices.
2) The minimum non-isomorphic cyclic graphs with same DD
The minimum non-isomorphic cyclic graphs with same distance distribution are the following graphs with 4 vertices (see Figure 3).
Note that, for the above graphs with same distance distribution, their Wiener matrix sequences and hyper-Wiener matrices are different.
The following theorem gives a class of graphs with same distance distribution.
Let be the set of all the graphs with vertices and edges.
Theorem 3.1. Let , and . Then .
Proof. Since and , we have
Figure 2. , , . , , .
Figure 3. , , .
for , and so .
Corollary 3.2. If , then all graphs in have same
Proof. For with , clearly .
We assert that .
Otherwise, there exist two vertices such that . Let be a shortest -path. Then any vertex not on is not adjacent to at least one of and , and the number of pairs of non-adjacent vertices on is equal to . So
, contradicting that .
Hence, by Theorem 3.1, if , all graphs in have same
distance distribution. □
Let denote the graph obtained from vertex-disjoint graphs and by connecting every vertex of to every vertex of .
Corollary 3.3. Let and . Then and have same distance distribution.
Proof. Obviously, , , and
. By Theorem 3.1,
For graphs with diameter greater than or equal to 2, we will give some construction methods for finding graphs with same distance distribution.
Let be a connected graph with vertices set , and let be the distant matrix of the graph G. Let denote the number of the vertices at distance from a vertex in , and let ) be the distance distribution of in .
Theorem 3.4. Let and (resp. and ) be the connected graphs with (resp. ) vertices and with same distance distribution. For , , , and , let (resp. ) be the graph ob- tained from and (resp. and ) by identifying and (resp. and ). If and , then and have same distance distribution.
Proof. It is enough to prove for .
Clearly, . Similarly,
, , , , we have for . Hence . □
Theorem 3.5. Let , , and let such that any two vertices in have distance less than or equal to 2 in , and . Let denote the graph obtained from by contracting vertices in to a vertex . Let be the graph obtained from by adding a new vertex and connecting to every vertex in . If and , then .
Proof. Clearly, by the conditions of the theorem, , . So, if and and
, then . □
From Theorem 3.4, we have the following corollary:
Corollary 3.6. Let and . Let be a con- nected graph vertex-disjoint with and . For , , and , let (resp. ) be the graph obtained from (resp. ) and by identifying and (resp. and ). If , then and have same distance distribution.
From Theorem 3.5, one can obtain graphs with same distance distribution in from graphs in with same distance distribution by adding a new vertex and some edges.
Figure 4 shows two pairs of graphs with 5 vertices and 5 edges and with same , one of which has diameter 2 and the other has diameter 3.
Figure 5 shows three pairs of graphs with 6 vertices and 6 edges and with
Figure 4. , , . , , .
Figure 5. , , . , , . , , .
same , two of which have diameter 3 and the other has diameter 4.
However, the construction methods are not complete. There might be some graphs with same which could not be obtained by the above construction methods.
Open Problem. Is there a construction method for finding all graphs with same distance distribution?
This work is jointly supported by the Natural Science Foundation of China (11101187, 61573005, 11361010), the Scientific Research Fund of Fujian Provincial Education Department of China (JAT160691).