On Graphs with Same Distance Distribution

Xiuliang Qiu^1*, Xiaofeng Guo^2,3

¹Chengyi University College, Jimei University, Xiamen, China.
²School of Mathematical Sciences, Xiamen University, Xiamen, China.

DOI: 10.4236/am.2017.86062                

Abstract

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.

Keywords

Distance Distribution, Distance Matrix, Wiener Vector, Hyper-Wiener Vector

1. Introduction

The Wiener index is one of the oldest topological indices of molecular structures. It was put forward by the physico-chemist Harold Wiener [1] in 1947. The Wiener index of a connected graph $G$ is defined as the sum of distances between all pairs of vertices in $G$ :

$W=W\left(G\right)={\displaystyle \underset{\left\{u,v\right\}\subseteq V\left(G\right)}{\sum }}{d}_G\left(u,v\right).$

where $V\left(G\right)$ is the vertex set of $G$ , and $d_G\left(u\mathrm{,}v\right)$ is the distance between vertices $u$ and $v$ in $G$ .

As an extension of the Wiener index of a tree, Randić [2] introduced Wiener matrix $W$ and hyper-Wiener index $R$ of a tree. For any two vertices $i\mathrm{,}j$ in $T$ , let $\pi \left(i\mathrm{,}j\right)$ denote the unique path in $T$ with end vertices $i\mathrm{,}j$ and the length $d_{ij}$ , let $T_{\mathrm{1,}\pi \left(i\mathrm{,}j\right)}$ and $T_{\mathrm{2,}\pi \left(i\mathrm{,}j\right)}$ denote the components of $T-E\left(\pi \left(i\mathrm{,}j\right)\right)$ containing $i$ and $j$ , respectively, and let $n_{\mathrm{1,}\pi \left(i\mathrm{,}j\right)}$ and $n_{\mathrm{2,}\pi \left(i\mathrm{,}j\right)}$ denote the numbers of the vertices in $T_{\mathrm{1,}\pi \left(i\mathrm{,}j\right)}$ and $T_{\mathrm{2,}\pi \left(i\mathrm{,}j\right)}$ , respectively. Then the Wiener matrix $W$ and the hyper-Wiener number $R$ of $T$ can be given by $W=\left(w_{ij}\right)$ , $w_{ij}=n_{1,\pi \left(i,j\right)}\cdot n_{2,\pi \left(i,j\right)}$ , and $R={\displaystyle {\sum }_{i<j}}{w}_{ij}$ .

In Refs. [3] [4] , Randic and Guo and colleagues further introduced the higher Wiener numbers and some other Wiener matrix invariants of a tree $T$ . The higher Wiener numbers can be represented by a Wiener number sequence ${}^{1}W{,}^{2}W{,}^{3}W\mathrm{,}\cdots$ , where ${}^{k}W={\displaystyle {\sum }_{d_{i,j}=k,i<j}}{w}_{ij}$ . It is not difficult to see ${}^{1}W=W$ , and $R={{\displaystyle {\sum }_{k=1,2,\cdots }}}^{k}W$ .

After the hyper-Wiener index of a tree was introduced, many publications [5] - [11] have appeared on calculation and generalization of the hyper-Wiener index. Klein et al. [5] generalized the hyper-Wiener index so as to be applicable to any connected structure. Their formula for the hyper-Wiener index $R$ of a graph $G$ is

$R=R\left(G\right)=\frac{1}{2}{\displaystyle \underset{\left\{u\mathrm{,}v\right\}\subseteq V\left(G\right)}{\sum }}\left(d_G^2\left(u,v\right)+d_G\left(u,v\right)\right).$

The relation between Hyper-Wiener and Wiener index was given by Gutman [11] .

The Hosoya polynomial $H\left(G\right)$ of a connected graph $G$ was introduced by Hosoya [12] in 1988, which he named as the Wiener polynomial of a graph:

$H=H\left(G,x\right)={\displaystyle \underset{k\ge 0}{\sum }}d\left(G,k\right)x^k,$

where $d\left(G\mathrm{,}k\right)$ is the number of pairs of vertices in the graph $G$ that are distance $k$ apart.

In Ref. [13] , Cash introduced a new hyper-Hosoya polynomial

$HH=HH\left(G,x\right)={\displaystyle \underset{k\ge 0}{\sum }}\frac{\left(k+1\right)}{2}d\left(G,k\right)x^k.$

The relationship between the Hosoya polynomial and the Hyper-Hosoya polynomial was discussed [13] .

The sequence $\left(d\left(G\mathrm{,1}\right)\mathrm{,}d\left(G\mathrm{,2}\right)\mathrm{,}\cdots \right)$ is also known (since 1981) as the dis- tance distribution of a graph $G$ [14] , denoted by $DD\left(G\right)$ . It is easy to see that $W={\displaystyle {\sum }_{k\ge 0}}k\cdot d\left(G,k\right)$ .

Later the definition of higher Wiener numbers is extended to be applicable to any connected structure by Guo et al. [15] . For a connected graph $G$ with n vertices, denoted by $\mathrm{1,2,}\cdots \mathrm{,}n$ , let $w_{ij,k}=\max \left\{d_{ij}-k+1,0\right\}$ where $d_{ij}$ is the distance between vertices $i$ and $j$ . Then ${}^{k}W={\displaystyle {\sum }_{i<j}}{w}_{ij,k}$ , $k=1,2,\cdots$ , are called the higher Wiener numbers of $G$ . The vector $\left({}^{1}W{\mathrm{,}}^{2}W\mathrm{,}\cdots \right)$ is called the hyper-Wiener vector of $G$ , denoted by $HWV\left(G\right)$ . The concept of the Wiener vector of a graph is also introduced in ref. [15] . For a connected graph $G$ with $n$ vertices, denoted by $\mathrm{1,2,}\cdots \mathrm{,}n$ , let $W_k={\displaystyle {\sum }_{i<j,d\left(ij\right)=k}}{d}_{ij}$ , $k=1,2,\cdots$ . The vector $\left(W_1\mathrm{,}{W}_2\mathrm{,}\cdots \right)$ is called the Wiener vector of $G$ , denoted by $WV\left(G\right)$ .

Moreover, a matrix sequence $\left(W^{\left(1\right)}\mathrm{,}{W}^{\left(2\right)}\mathrm{,}{W}^{\left(3\right)}\mathrm{,}\cdots \right)$ , called the Wiener matrix sequence, and their sum ${\displaystyle {\sum }_{k=1,2,\cdots }}{W}^{\left(k\right)}=W^{\left(H\right)}$ , called the hyper-Wiener matrix, are introduced, where $W^{\left(1\right)}=D$ 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. [15] , we study the relation between Wiener number $W$ , hyper-Wiener number $R$ , Wiener vector $WV$ , hyper- Wiener vector $HWV$ , Hosoya polynomial $H$ , hyper-Hosoya polynomial $HH$ and distance distribution $DD$ of a graph. It is shown that for connected graphs $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ , 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 $W,R,WV,HWV,H,HH,DD$

Let $diam\left(G\right)$ denote the diameter of a graph $G$ .

Theorem 2.1. Let $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ be connected graphs. Then the following five statements are equivalent:

1) $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same distance distribution $DD$ ;

2) $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same Wiener vector $WV$ ;

3) $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same hyper-Wiener vector $HWV$ ;

4) $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same Wiener polynomial $H$ ;

5) $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same hyper-Wiener polynomial $HH$ .

Proof. We shall show the equivalent statements by (1)Þ(2)Þ(3)Þ(4)Þ(5)Þ(1).

(1)Þ(2). By the definitions of $DD$ and $WV$ ,

$DD\left(G\right)=\left(d\left(G\mathrm{,1}\right)\mathrm{,}d\left(G\mathrm{,2}\right)\mathrm{,}\cdots \mathrm{,}d\left(G\mathrm{,}diam\left(G\right)\right)\right)$ , and

$WV\left(G\right)=\left(W_1\mathrm{,}{W}_2\mathrm{,}\cdots \mathrm{,}{W}_{diam\left(G\right)}\right)=\left(1d\left(G\mathrm{,1}\right)\mathrm{,2}d\left(G\mathrm{,2}\right)\mathrm{,}\cdots \mathrm{,}diam\left(G\right)d\left(G\mathrm{,}diam\left(G\right)\right)\right)$ .

Clearly, if $DD\left(G\right)=DD\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ , then $WV\left(G\right)=WV\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ .

(2)Þ(3). If $WV\left(G\right)=WV\left(G^{*}\right)$ , then $W_k={\displaystyle {\sum }_{i<j,d_{ij}=k}}{d}_{ij}=W_k^{*}={\displaystyle {\sum }_{i<j,d_{ij}^{*}=k}}{d}_{ij}^{*}$ for $k=1,2,\cdots ,diam\left(G\right)$ . So ${}^{k}W={\displaystyle {\sum }_{i<j}}{w}_{ij,k}={\displaystyle {\sum }_{i<j}}\max \left\{d_{ij}-k+1,0\right\}={\displaystyle {\sum }_{i<j}}\max \left\{d_{ij}^{*}-k+1,0\right\}={\displaystyle {\sum }_{i<j}}{w}_{ij,k}^{*}={}^{k}W{}^{*}$ for $k=1,2,\cdots ,diam\left(G\right)$ . Hence $HWV\left(G\right)=HWV\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ .

(3)Þ(4). Suppose $HWV\left(G\right)=HWV\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ . Then ${}^{k}W={}^{k}W{}^{*}$ for $k=1,2,\cdots$ , and $diam\left(G\right)=diam\left(G^{*}\right)$ .

If $k=diam\left(G\right)=diam\left(G^{*}\right)$ , then

$\begin{array}{c}{}^{k}W={\displaystyle {\sum }_{i<j}}\max \left\{d_{ij}-k+1,0\right\}=d\left(G,diam\left(G\right)\right)\\ ={}^{k}W{}^{*}={\displaystyle {\sum }_{i<j}}\max \left\{d_{ij}^{*}-k+1,0\right\}=d\left(G^{*},diam\left(G^{*}\right)\right)\end{array}$ .

Assume, for $1<l\le k\le diam\left(G\right)$ , $d\left(G,k\right)=d\left(G^{*},k\right)$ . Let $k=l-1$ . Then

$\begin{array}{c}{}^{l-1}W={\displaystyle {\sum }_{i<j}}\max \left\{d_{ij}-l+2,0\right\}=d\left(G,l-1\right)+{\displaystyle {\sum }_{i<j,d_{ij}>l-1}}\max \left\{d_{ij}-l+2,0\right\}\\ =d\left(G,l-1\right)+{\displaystyle {\sum }_{i<j,d_{ij}=k^{\prime }>l-1}}d\left(G,k^{\prime }\right)\left(k^{\prime }-l+2\right)\end{array}$ , and

$\begin{array}{c}{}^{l-1}{W}^{*}={\displaystyle {\sum }_{i<j}}\max \left\{d_{ij}^{*}-l+2,0\right\}=d\left(G^{*},l-1\right)+{\displaystyle {\sum }_{i<j,d_{ij}^{*}>l-1}}\max \left\{d_{ij}^{*}-l+2,0\right\}\\ =d\left(G^{*},l-1\right)+{\displaystyle {\sum }_{i<j,d_{ij}^{*}=k^{\prime }>l-1}}d\left(G^{*},k^{\prime }\right)\left(k^{\prime }-l+2\right)={}^{l-1}W\end{array}$ .

By induction hypothesis,

${\displaystyle {\sum }_{i<j,d_{ij}=k^{\prime }>l-1}}d\left(G,k^{\prime }\right)\left(k^{\prime }-l+2\right)={\displaystyle {\sum }_{i<j,d_{ij}^{*}=k^{\prime }>l-1}}d\left(G^{*},k^{\prime }\right)\left(k^{\prime }-l+2\right)$ . So we have

$d\left(G,l-1\right)=d\left(G^{*},l-1\right)$ .

Now it follows that $d\left(G,k\right)=d\left(G^{*},k\right)$ for $k=1,2,\cdots$ , and so

$H\left(G,x\right)={\displaystyle {\sum }_{k\ge 0}}d\left(G,k\right)x^k={\displaystyle {\sum }_{k\ge 0}}d\left(G^{*},k\right)x^k=H\left(G^{*},x\right)$ .

(4)Þ(5). By the definitions of Hosoya polynomial $H$ and hyper-Hosoya polynomial $HH$ , it is easy to see that, if $H\left(G,x\right)=H\left(G^{*},x\right)$ , then $HH\left(G,x\right)=HH\left(G^{*},x\right)$ .

(5)Þ(1). If $HH\left(G,x\right)=HH\left(G^{*},x\right)$ , then $d\left(G,k\right)=d\left(G^{*},k\right)$ for $k=1,2,\cdots$ . Therefore $DD\left(G\right)=DD\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ . □

Theorem 2.2. Let $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ be two graphs with same distance dis- tribution. Then $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same $W$ and $R$ .

Proof: By the definitions of $DD$ , $W$ and $R$ ,

$DD\left(G\right)=\left(d\left(G\mathrm{,1}\right)\mathrm{,}d\left(G\mathrm{,2}\right)\mathrm{,}\cdots \mathrm{,}d\left(G\mathrm{,}diam\left(G\right)\right)\right)$ , $W\left(G\right)\mathrm{<mo>\; =\; </mo>}{\displaystyle {\sum }_{\left\{u\mathrm{,}v\right\}\subseteq V\left(G\right)}}{d}_G\left(u\mathrm{,}v\right)$ ,

and $R\left(G\right)=\frac{1}{2}{\displaystyle {\sum }_{\left\{u\mathrm{,}v\right\}\subseteq V\left(G\right)}}\left(d_G^2\left(u,v\right)+d_G\left(u,v\right)\right)$ .

Clearly, if $DD\left(G\right)=DD\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ , then $W\left(G\right)=W\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ and $R\left(G\right)=R\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ . ,

However, the contrary of the theorem doesn’t hold. For instance, the trees $T_1$ and $T_1^{\mathrm{<mo>\; *\; </mo>}}$ (resp. $T_2$ and $T_2^{\mathrm{<mo>\; *\; </mo>}}$ ) in Figure 1 have same $W$ and $R$ , but they have different distance distributions.

3. Graphs with Same Distance Distribution

From the above theorems, one can see that, if two graphs $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have

Figure 1. $W\left(T_1\right)=W\left(T_1^{\mathrm{<mo>\; *\; </mo>}}\right)=86$ , $R\left(T_1\right)=R\left(T_1^{\mathrm{<mo>\; *\; </mo>}}\right)=166$ , $DD\left(T_1\right)=\left(8,14,6,8\right)$ , $DD\left(T_1^{*}\right)=\left(8,13,9,5,1\right)$ . $W\left(T_2\right)=W\left(T_2^{\mathrm{<mo>\; *\; </mo>}}\right)=98$ , $R\left(T_2\right)=R\left(T_2^{\mathrm{<mo>\; *\; </mo>}}\right)=217$ , $DD\left(T_2\right)=\left(8,10,8,5,4,1\right)$ , $DD\left(T_2^{*}\right)=\left(8,11,6,5,6\right)$ .

same distance distribution $DD$ , then they have same $W\mathrm{,}WW\mathrm{,}WV\mathrm{,}HWV\mathrm{,}H$ and $HH$ . 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 ${\mathcal{G}}_{n\mathrm{,}m}$ be the set of all the graphs with $n$ vertices and $m$ edges.

Theorem 3.1. Let $G\mathrm{,}{G}^{\mathrm{<mo>\; *\; </mo>}}\in {\mathcal{G}}_{n\mathrm{,}m}$ , and $diam\left(G\right)=diam\left(G^{*}\right)=2$ . Then $DD\left(G\right)=DD\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ .

Proof. Since $G\mathrm{,}{G}^{\mathrm{<mo>\; *\; </mo>}}\in {\mathcal{G}}_{n\mathrm{,}m}$ and $diam\left(G\right)=diam\left(G^{*}\right)=2$ , we have

Figure 2. $W\left(T_3\right)=W\left(T_3^{*}\right)=82$ , $R\left(T_3\right)=R\left(T_3^{*}\right)=149$ , $DD\left(T_3\right)=DD\left(T_3^{*}\right)=\left(8,13,12,3\right)$ . $W\left(T_4\right)=W\left(T_4^{\mathrm{<mo>\; *\; </mo>}}\right)=92$ , $R\left(T_4\right)=R\left(T_4^{\mathrm{<mo>\; *\; </mo>}}\right)=188$ , $DD\left(T_4\right)=DD\left(T_4^{*}\right)=\left(8,10,10,6,2\right)$ .

Figure 3. $W\left(G_1\right)=W\left(G_1^{*}\right)=8$ , $R\left(G_1\right)=R\left(G_1^{*}\right)=10$ , $DD\left(G_1\right)=DD\left(G_1^{*}\right)=\left(4,2\right)$ .

$d\left(G,1\right)=d\left(G^{*},1\right)=m$ , $d\left(G,2\right)=d\left(G^{*},2\right)=\left(\begin{array}{c}n\\ 2\end{array}\right)-m$ , $d\left(G,k\right)=d\left(G^{*},k\right)=0$

for $k\ge 3$ , and so $DD\left(G\right)=DD\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ .

Corollary 3.2. If $\left(\begin{array}{c}n\\ 2\end{array}\right)>m>\left(\begin{array}{c}n\\ 2\end{array}\right)-n+1$ , then all graphs in ${\mathcal{G}}_{n\mathrm{,}m}$ have same

distance distribution.

Proof. For $\forall G\in {\mathcal{G}}_{n\mathrm{,}m}$ with $\left(\begin{array}{c}n\\ 2\end{array}\right)>m>\left(\begin{array}{c}n\\ 2\end{array}\right)-n+1$ , clearly $diam\left(G\right)\ge 2$ .

We assert that $diam\left(G\right)=2$ .

Otherwise, there exist two vertices $u\mathrm{,}v\in V\left(G\right)$ such that $d\left(u\mathrm{,}v\right)\ge 3$ . Let $P$ be a shortest $\left(u\mathrm{,}v\right)$ -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 $\left(\left|V\left(P\right)\right|-2\right)+\left(\left|V\left(P\right)\right|-3\right)+\cdots +1=\left(\left|V\left(P\right)\right|-2\right)\left(\left|V\left(P\right)\right|-1\right)/2$ . So

$\begin{array}{c}m\le \left(\begin{array}{c}n\\ 2\end{array}\right)-\left(n-\left|V\left(P\right)\right|\right)-\left(\left|V\left(P\right)\right|-2\right)\left(\left|V\left(P\right)\right|-1\right)/2\\ =\left(\begin{array}{c}n\\ 2\end{array}\right)-n-\left[\left(\left|V\left(P\right)\right|-2\right)\left(\left|V\left(P\right)\right|-3\right)-4\right]/2\le \left(\begin{array}{c}n\\ 2\end{array}\right)-n+1\end{array}$ , contradicting that $m>\left(\begin{array}{c}n\\ 2\end{array}\right)-n+1$ .

Hence, by Theorem 3.1, if $m>\left(\begin{array}{c}n\\ 2\end{array}\right)-n+1$ , all graphs in ${\mathcal{G}}_{n\mathrm{,}m}$ have same

distance distribution. □

Let $GVH$ 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\mathrm{,}{G}_2^1\in {\mathcal{G}}_{n_1\mathrm{,}{m}_1}$ and $G_1^2\mathrm{,}{G}_2^2\in {\mathcal{G}}_{n_2\mathrm{,}{m}_2}$ . Then $G_1^{1}V{G}_1^2$ and $G_2^{1}V{G}_2^2$ have same distance distribution.

Proof. Obviously, $\left|V\left(G_1^{1}V{G}_1^2\right)\right|=\left|V\left(G_2^{1}V{G}_2^2\right)\right|=n_1+n_2$ , $diam\left(G_1^{1}V{G}_1^2\right)=diam\left(G_2^{1}V{G}_2^2\right)=2$ , and

$\left|E\left(G_1^{1}V{G}_1^2\right)\right|=\left|E\left(G_2^{1}V{G}_2^2\right)\right|=m_1+m_2+n_1\cdot n_2$ . By Theorem 3.1,

$DD\left(G_1^{1}V{G}_1^2\right)=DD\left(G_2^{1}V{G}_2^2\right)$ .

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 $\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ , and let $D\left(G\right)=\left(d_{ij}\right)$ be the distant matrix of the graph G. Let $d_k^G\left(v_i\right)$ denote the number of the vertices at distance $k$ from a vertex $v_i$ in $G$ , and let $D{D}_G\left(v_i\right)=\left(d_1^G\left(v_i\right),d_2^G\left(v_i\right),\cdots ,d_{diam\left(G\right)}^G\left(v_i\right)\right)$ ) be the distance distribution of $v_i$ in $G$ .

Theorem 3.4. Let $G_1$ and $G_2$ (resp. ${G^{\prime }}_1$ and ${G^{\prime }}_2$ ) be the connected graphs with $n_1$ (resp. $n_2$ ) vertices and with same distance distribution. For $v_1\in V\left(G_1\right)$ , $v_2\in V\left(G_2\right)$ , ${v^{\prime }}_1\in V\left({G^{\prime }}_1\right)$ , and ${v^{\prime }}_2\in V\left({G^{\prime }}_2\right)$ , let $G$ (resp. $G^{\mathrm{<mo>\; *\; </mo>}}$ ) be the graph ob- tained from $G_1$ and ${G^{\prime }}_1$ (resp. $G_2$ and ${G^{\prime }}_2$ ) by identifying $v_1$ and ${v^{\prime }}_1$ (resp. $v_2$ and ${v^{\prime }}_2$ ). If $D{D}_{G_1}\left(v_1\right)=D{D}_{G_2}\left(v_2\right)$ and $D{D}_{{G^{\prime }}_1}\left({v^{\prime }}_1\right)=D{D}_{{G^{\prime }}_2}\left({v^{\prime }}_2\right)$ , then $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same distance distribution.

Proof. It is enough to prove $d\left(G,k\right)=d\left(G^{*},k\right)$ for $k=1,2,\cdots$ .

Clearly, $d\left(G,k\right)=d\left(G_1,k\right)+d\left({G^{\prime }}_1,k\right)+{\displaystyle {\sum }_{1\le i,j\le k,i+j=k}}{d}_i^{G_1}\left(v_1\right)d_j^{{G^{\prime }}_1}\left({v^{\prime }}_1\right)$ . Similarly,

$d\left(G^{*},k\right)=d\left(G_2,k\right)+d\left({G^{\prime }}_2,k\right)+{\displaystyle {\sum }_{1\le i,j\le k,i+j=k}}{d}_i^{G_2}\left(v_2\right)d_j^{{G^{\prime }}_2}\left({v^{\prime }}_2\right)$ . Because

$DD\left(G_1\right)=DD\left(G_2\right)$ , $DD\left({G^{\prime }}_1\right)=DD\left({G^{\prime }}_2\right)$ , $D{D}_{G_1}\left(v_1\right)=D{D}_{G_2}\left(v_2\right)$ , $D{D}_{{G^{\prime }}_1}\left({v^{\prime }}_1\right)=D{D}_{{G^{\prime }}_2}\left({v^{\prime }}_2\right)$ , we have $d\left(G,k\right)=d\left(G^{*},k\right)$ for $k=1,2,\cdots$ . Hence $DD\left(G\right)=DD\left(G^{\mathrm{<mo>\; *\; </mo>}}\right)$ . □

Theorem 3.5. Let $G_i\in {\mathcal{G}}_{n\mathrm{,}m}$ , $i=1,2$ , and let $S_i\subset V\left(G_i\right)$ such that any two vertices in $S_i$ have distance less than or equal to 2 in $G_i$ , and $\left|S_1\right|=\left|S_2\right|$ . Let $G_i\left\{S_i\right\}$ denote the graph obtained from $G_i$ by contracting vertices in $S_i$ to a vertex $s_i$ . Let $G_i^{\mathrm{<mo>\; *\; </mo>}}$ 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 $DD\left(G_1\right)=DD\left(G_2\right)$ and $D{D}_{G_1\left\{S_1\right\}}\left(s_1\right)=D{D}_{G_2\left\{S_2\right\}}\left(s_2\right)$ , then $DD\left(G_1^{*}\right)=DD\left(G_2^{*}\right)$ .

Proof. Clearly, by the conditions of the theorem, $DD\left(G_i^{*}\right)=DD\left(G_i\right)+D{D}_{G_i^{*}}\left(x_i\right)=DD\left(G_i\right)+\left(\left|S_i\right|,1+d_1^{G_i\left\{S_i\right\}}\left(x_i\right),1+d_2^{G_i\left\{S_i\right\}}\left(x_i\right),\cdots \right)$ , $i=1,2$ . So, if $DD\left(G_1\right)=DD\left(G_2\right)$ and $DD\left({G^{\prime }}_1\right)=DD\left({G^{\prime }}_2\right)$ and

$D{D}_{G_1\left\{S_1\right\}}\left(s_1\right)=D{D}_{G_2\left\{S_2\right\}}\left(s_2\right)$ , then $D{D}_{G_1^{*}}=D{D}_{G_2^{*}}$ . □

From Theorem 3.4, we have the following corollary:

Corollary 3.6. Let $G_1\mathrm{,}{G}_2\in {\mathcal{G}}_{n\mathrm{,}m}$ and $DD\left(G_1\right)=DD\left(G_2\right)$ . Let $H$ be a con- nected graph vertex-disjoint with $G_1$ and $G_2$ . For $v_1\in V\left(G_1\right)$ , $v_2\in V\left(G_2\right)$ , and $u\in V\left(H\right)$ , let $G$ (resp. $G^{\mathrm{<mo>\; *\; </mo>}}$ ) 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}\left(v_1\right)=D{D}_{G_2}\left(v_2\right)$ , then $G$ and $G^{\mathrm{<mo>\; *\; </mo>}}$ have same distance distribution.

From Theorem 3.5, one can obtain graphs with same distance distribution in ${\mathcal{G}}_{n\mathrm{,}m}$ from graphs in ${\mathcal{G}}_{n-\mathrm{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 $DD$ , 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\left(G_2\right)=W\left(G_2^{*}\right)=15$ , $R\left(G_2\right)=R\left(G_2^{*}\right)=20$ , $DD\left(G_2\right)=DD\left(G_2^{*}\right)=\left(5,5\right)$ . $W\left(G_3\right)=W\left(G_3^{*}\right)=16$ , $R\left(G_3\right)=R\left(G_3^{*}\right)=23$ , $DD\left(G_3\right)=DD\left(G_3^{*}\right)=\left(5,4,1\right)$ .

Figure 5. $W\left(G_4\right)=W\left(G_4^{*}\right)=26$ , $R\left(G_4\right)=R\left(G_4^{*}\right)=39$ , $DD\left(G_4\right)=DD\left(G_4^{*}\right)=\left(6,7,2\right)$ . $W\left(G_5\right)=W\left(G_5^{*}\right)=27$ , $R\left(G_5\right)=R\left(G_5^{*}\right)=42$ , $DD\left(G_5\right)=DD\left(G_5^{*}\right)=\left(6,6,3\right)$ . $W\left(G_6\right)=W\left(G_6^{*}\right)=29$ , $R\left(G_6\right)=R\left(G_6^{*}\right)=49$ , $DD\left(G_6\right)=DD\left(G_6^{*}\right)=\left(6,5,3,1\right)$ .

same $DD$ , 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 $DD$ 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).

Conflicts of Interest

The authors declare no conflicts of interest.

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