) = d ( G * , 1 ) = m , d ( G , 2 ) = d ( G * , 2 ) = ( n 2 ) m , d ( G , k ) = d ( G * , k ) = 0

for k 3 , and so D D ( G ) = D D ( G * ) .

Corollary 3.2. If ( n 2 ) > m > ( n 2 ) n + 1 , then all graphs in G n , m have same

distance distribution.

Proof. For G G n , m with ( n 2 ) > m > ( n 2 ) n + 1 , clearly d i a m ( G ) 2 .

We assert that d i a m ( G ) = 2 .

Otherwise, there exist two vertices u , v V ( G ) such that d ( u , v ) 3 . Let P be a shortest ( u , v ) -path. Then any vertex not on P is not adjacent to at least one of u and v , and the number of pairs of non-adjacent vertices on P is equal to ( | V ( P ) | 2 ) + ( | V ( P ) | 3 ) + + 1 = ( | V ( P ) | 2 ) ( | V ( P ) | 1 ) / 2 . So

m ( n 2 ) ( n | V ( P ) | ) ( | V ( P ) | 2 ) ( | V ( P ) | 1 ) / 2 = ( n 2 ) n [ ( | V ( P ) | 2 ) ( | V ( P ) | 3 ) 4 ] / 2 ( n 2 ) n + 1 , contradicting that m > ( n 2 ) n + 1 .

Hence, by Theorem 3.1, if m > ( n 2 ) n + 1 , all graphs in G n , m have same

distance distribution. □

Let G V H denote the graph obtained from vertex-disjoint graphs G and H by connecting every vertex of G to every vertex of H .

Corollary 3.3. Let G 1 1 , G 2 1 G n 1 , m 1 and G 1 2 , G 2 2 G n 2 , m 2 . Then G 1 1 V G 1 2 and G 2 1 V G 2 2 have same distance distribution.

Proof. Obviously, | V ( G 1 1 V G 1 2 ) | = | V ( G 2 1 V G 2 2 ) | = n 1 + n 2 , d i a m ( G 1 1 V G 1 2 ) = d i a m ( G 2 1 V G 2 2 ) = 2 , and

| E ( G 1 1 V G 1 2 ) | = | E ( G 2 1 V G 2 2 ) | = m 1 + m 2 + n 1 n 2 . By Theorem 3.1,

D D ( G 1 1 V G 1 2 ) = D D ( G 2 1 V G 2 2 ) .

For graphs with diameter greater than or equal to 2, we will give some construction methods for finding graphs with same distance distribution.

Let G be a connected graph with vertices set { v 1 , v 2 , , v n } , and let D ( G ) = ( d i j ) be the distant matrix of the graph G. Let d k G ( v i ) denote the number of the vertices at distance k from a vertex v i in G , and let D D G ( v i ) = ( d 1 G ( v i ) , d 2 G ( v i ) , , d d i a m ( G ) G ( v i ) ) ) be the distance distribution of v i in G .

Theorem 3.4. Let G 1 and G 2 (resp. G 1 and G 2 ) be the connected graphs with n 1 (resp. n 2 ) vertices and with same distance distribution. For v 1 V ( G 1 ) , v 2 V ( G 2 ) , v 1 V ( G 1 ) , and v 2 V ( G 2 ) , let G (resp. G * ) be the graph ob- tained from G 1 and G 1 (resp. G 2 and G 2 ) by identifying v 1 and v 1 (resp. v 2 and v 2 ). If D D G 1 ( v 1 ) = D D G 2 ( v 2 ) and D D G 1 ( v 1 ) = D D G 2 ( v 2 ) , then G and G * have same distance distribution.

Proof. It is enough to prove d ( G , k ) = d ( G * , k ) for k = 1 , 2 , .

Clearly, d ( G , k ) = d ( G 1 , k ) + d ( G 1 , k ) + 1 i , j k , i + j = k d i G 1 ( v 1 ) d j G 1 ( v 1 ) . Similarly,

d ( G * , k ) = d ( G 2 , k ) + d ( G 2 , k ) + 1 i , j k , i + j = k d i G 2 ( v 2 ) d j G 2 ( v 2 ) . Because

D D ( G 1 ) = D D ( G 2 ) , D D ( G 1 ) = D D ( G 2 ) , D D G 1 ( v 1 ) = D D G 2 ( v 2 ) , D D G 1 ( v 1 ) = D D G 2 ( v 2 ) , we have d ( G , k ) = d ( G * , k ) for k = 1 , 2 , . Hence D D ( G ) = D D ( G * ) . □

Theorem 3.5. Let G i G n , m , i = 1 , 2 , and let S i V ( G i ) such that any two vertices in S i have distance less than or equal to 2 in G i , and | S 1 | = | S 2 | . Let G i { S i } denote the graph obtained from G i by contracting vertices in S i to a vertex s i . Let G i * be the graph obtained from G i by adding a new vertex x i and connecting x i to every vertex in S i . If D D ( G 1 ) = D D ( G 2 ) and D D G 1 { S 1 } ( s 1 ) = D D G 2 { S 2 } ( s 2 ) , then D D ( G 1 * ) = D D ( G 2 * ) .

Proof. Clearly, by the conditions of the theorem, D D ( G i * ) = D D ( G i ) + D D G i * ( x i ) = D D ( G i ) + ( | S i | , 1 + d 1 G i { S i } ( x i ) , 1 + d 2 G i { S i } ( x i ) , ) , i = 1 , 2 . So, if D D ( G 1 ) = D D ( G 2 ) and D D ( G 1 ) = D D ( G 2 ) and

D D G 1 { S 1 } ( s 1 ) = D D G 2 { S 2 } ( s 2 ) , then D D G 1 * = D D G 2 * . □

From Theorem 3.4, we have the following corollary:

Corollary 3.6. Let G 1 , G 2 G n , m and D D ( G 1 ) = D D ( G 2 ) . Let H be a con- nected graph vertex-disjoint with G 1 and G 2 . For v 1 V ( G 1 ) , v 2 V ( G 2 ) , and u V ( H ) , let G (resp. G * ) be the graph obtained from G 1 (resp. G 2 ) and H by identifying v 1 and u (resp. v 2 and u ). If D D G 1 ( v 1 ) = D D G 2 ( v 2 ) , then G and G * have same distance distribution.

From Theorem 3.5, one can obtain graphs with same distance distribution in G n , m from graphs in G n 1, m s 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 D D , 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. W ( G 2 ) = W ( G 2 * ) = 15 , R ( G 2 ) = R ( G 2 * ) = 20 , D D ( G 2 ) = D D ( G 2 * ) = ( 5 , 5 ) . W ( G 3 ) = W ( G 3 * ) = 16 , R ( G 3 ) = R ( G 3 * ) = 23 , D D ( G 3 ) = D D ( G 3 * ) = ( 5 , 4 , 1 ) .

Figure 5. W ( G 4 ) = W ( G 4 * ) = 26 , R ( G 4 ) = R ( G 4 * ) = 39 , D D ( G 4 ) = D D ( G 4 * ) = ( 6 , 7 , 2 ) . W ( G 5 ) = W ( G 5 * ) = 27 , R ( G 5 ) = R ( G 5 * ) = 42 , D D ( G 5 ) = D D ( G 5 * ) = ( 6 , 6 , 3 ) . W ( G 6 ) = W ( G 6 * ) = 29 , R ( G 6 ) = R ( G 6 * ) = 49 , D D ( G 6 ) = D D ( G 6 * ) = ( 6 , 5 , 3 , 1 ) .

same D D , 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 D D 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?

Acknowledgements

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).

Cite this paper
Qiu, X. and Guo, X. (2017) On Graphs with Same Distance Distribution. Applied Mathematics, 8, 799-807. doi: 10.4236/am.2017.86062.
References

[1]   Wiener, H. (1947) Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69, 17-20.
https://doi.org/10.1021/ja01193a005

[2]   Randic, M. (1993) Novel Molecular Descriptor for Structure-Property Studies. Chemical Physics Letters, 211, 478-483.
https://doi.org/10.1016/0009-2614(93)87094-J

[3]   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.
https://doi.org/10.1021/ci00015a008

[4]   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.
https://doi.org/10.1021/ci00018a022

[5]   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.
https://doi.org/10.1021/ci00023a007

[6]   Lukovits, I. and Linert, W. (1995) A Novel Definition of the Hyper-Wiener Index for Cycles. Journal of Chemical Information and Computer Sciences, 34, 899-902.
https://doi.org/10.1021/ci00020a025

[7]   Klein, D.J. and Randic, M. (1993) Resistance Distance. Journal of Mathematical Chemistry, 12, 81-95.
https://doi.org/10.1007/BF01164627

[8]   Li, X.H. (2003) The Extended Hyper-Wiener Index. Canadian Journal of Chemistry, 81, 992-996.
https://doi.org/10.1139/v03-106

[9]   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.
https://doi.org/10.1021/ci00025a030

[10]   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.
https://doi.org/10.1021/ci0100999

[11]   Gutman, I. (2002) Relation between Hyper-Wiener and Wiener Index. Chemical Physics Letters, 364, 352-356.
https://doi.org/10.1016/S0009-2614(02)01343-X

[12]   Hosoya, H. (1998) On Some Counting Polynominals in Chemistry. Discrete Applied Mathematics, 19, 239-257.

[13]   Cash, G.G. (2002) Relationship between the Hosoya Polynominal and the Hyper-Wiener Index. Applied Mathematics Letters, 15, 893-895.

[14]   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.

[15]   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.
https://doi.org/10.1002/qua.20958

 
 
Top