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.
It is easy to see that the graphs in Figure 5 can be obtained from graphs in Figure 3, Figure 4 by the construction methods given in Theorems 3.4, 3.5.
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).
 Randic, M., Guo, X.F., Oxley, T. and Krishnapriyan, H. (1993) Wiener Matrix: Source of Novel Graph Invariants. Journal of Chemical Information and Computer Sciences, 33, 709-716.
 Randic, M., Guo, X.F., Oxley, T., Krishnapriyan, h. and Naylor, L. (1994) Wiener Matrix Invariants. Journal of Chemical Information and Computer Sciences, 34, 361-367.
 Klein, D.J. and Gutman, I. (1995) On the Definition of the Hyper-Wiener Index for Cycle-Containing Structures. Journal of Chemical Information and Computer Sciences, 35, 50-52.
 Klavzar, S., Gutman, I. and Mohar, B. (1995) Labeling of Benzenoid Systems which Reflects the Vertex-Distance Relations. Journal of Chemical Information and Computer Sciences, 35, 590-593.
 Cash, G.G., Klavzar, S. and Petkovsek, M. (2002) Three Methods for Calculation of the Hyper-Wiener Index of Molecular Graphs. Journal of Chemical Information and Computer Sciences, 42, 571-576.
 Buckley, F. and Superville, L. (1981) Distance Distributions and Mean Distance Problem. Proceedings of Third Caribbean Conference on Combinatorics and Computing, University of the West Indies, Barbados, January 1981, 67-76.
 Guo, X.F., klein, D.J., Yan, W.G. and Yeh, Y.-N. (2006) Hyper-Wiener Vector, Wiener Matrix Sequence, and Wiener Polynominal Sequence of a Graph. International Journal of Quantum Chemistry, 106, 1756-1761.