A method for constructing graphs with the same resistance spectrum

Si-Ao Xu Huan Zhou Xiang-Feng Pan ¹¹1Funding:Xiang-Feng Pan was supported by Natural Science Foundation of Anhui Province under Grant No. 2108085MA02 and University Natural Science Research Project of Anhui Province under Grant No. KJ2020A0001. [email protected] School of Mathematical Sciences, Anhui University, Hefei, Anhui, 230601, P.R. China

Abstract

Let $G=(V(G),E(G))$ be a graph with vertex set $V(G)$ and edge set $E(G)$ . The resistance distance $R_{G}(x,y)$ between two vertices $x,y$ of $G$ is defined to be the effective resistance between the two vertices in the corresponding electrical network in which each edge of $G$ is replaced by a unit resistor. The resistance spectrum $\operatorname{RS}(G)$ of a graph $G$ is the multiset of the resistance distances of all pairs of vertices in the graph. This paper presents a method for constructing graphs with the same resistance spectrum. It is obtained that for any positive integer $k$ , there exist at least $2^{k}$ graphs with the same resistance spectrum. Furthermore, it is shown that for $n\geq 10$ , there are at least $2(n-9)p(n-9)$ pairs of graphs of order $n$ with the same resistance spectrum, where $p(n-9)$ is the number of partitions of the integer $n-9$ .

keywords:

Resistance distance, Resistance spectrum, Partition of positive integer

MSC:

[2010] 05C12, 05C76

^†^†journal:

1 Introduction

In 1993, Klein and Randić [1] introduced the concept of resistance distance based on the theory of electrical networks. The resistance distance $R_{G}(x,y)$ between two vertices $x$ and $y$ of a graph $G$ is defined as the effective resistance of the two points in the corresponding electrical network, which the electrical network is attained from $G$ by replacing each edge of the graph with a unit resistor.

The resistance spectrum $\operatorname{RS}(G)$ of a graph $G$ is defined as the multiset of the resistance distances of all pairs of vertices in the graph. The resistance spectrum of a graph had been initially used to solve the graph isomorphism problem by Baxter [2] who conjectured that two graphs are isomorphic if and only if their resistance spectra are identical. However, this conjecture had been quickly disproved after some counterexamples [3, 4] were found.

All nonisomorphic simple graphs with no more than $8$ vertices are determined by their resistance spectra. However, there are exactly $11$ and $49$ pairs of nonisomorphic graphs, each pair of which shares the same resistance spectrum, among all simple graphs with $9$ and $10$ vertices, respectively [5]. In addition, a number of other pairs with the same resistance spectrum but different structures have been discovered. Figure 1 illustrates $13$ such pairs of nonisomorphic graphs, whose resistance spectra are given in Table 1. The first $11$ pairs of graphs here are the ones with 9 vertices. The 2nd, 3rd, and 12th, 13th pairs were discovered by Baxter [3] and Rickard [4], respectively. A graph $G$ is said to be $DRS$ if it is determined by the resistance spectrum, that is, there is no nonisomorphic graph with the same resistance spectrum as $G$ ; conversely, if there is a nonisomorphic graph such that it has the same resistance spectrum as $G$ , then $G$ is said to be $non$ - $DRS$ .

Refer to caption — Figure 1: $13$ pairs of nonisomorphic graphs with the same resistance spectrum [5].

Table 1: Resistance spectra of the graphs [5].

Graph pair	Resistance spectrum
1	$[1]^{6}$ $[2]^{6}$ $[+\infty]^{24}$
2	$[2/3]^{3}$ $[1]^{6}$ $[5/3]^{12}$ $[2]^{6}$ $[8/3]^{9}$
3	$[1]^{8}$ $[2]^{13}$ $[3]^{12}$ $[4]^{3}$
4	$[3/4]^{8}$ $[1]^{6}$ $[3/2]^{4}$ $[7/4]^{8}$ $[2]^{4}$ $[11/4]^{4}$ $[3]^{2}$
5	$[1]^{6}$ $[2]^{4}$ $[3]^{2}$ $[+\infty]^{24}$
6	$[1]^{8}$ $[2]^{10}$ $[3]^{10}$ $[4]^{6}$ $[5]^{2}$
7	$[1/2]^{1}$ $[5/8]^{4}$ $[1]^{6}$ $[3/2]^{2}$ $[13/8]^{8}$ $[2]^{4}$ $[5/2]^{1}$ $[21/8]^{6}$ $[3]^{2}$ $[29/8]^{2}$
8	$[3/4]^{4}$ $[1]^{7}$ $[7/4]^{4}$ $[2]^{6}$ $[11/4]^{4}$ $[3]^{5}$ $[15/4]^{2}$ $[4]^{3}$ $[5]^{1}$
9	$[2/3]^{10}$ $[1]^{5}$ $[4/3]^{4}$ $[5/3]^{10}$ $[2]^{2}$ $[7/3]^{2}$ $[8/3]^{3}$
10	$[1/2]^{1}$ $[5/8]^{4}$ $[1]^{6}$ $[13/8]^{4}$ $[2]^{6}$ $[21/8]^{4}$ $[3]^{5}$ $[29/8]^{2}$ $[4]^{3}$ $[5]^{1}$
11	$[1/2]^{2}$ $[5/8]^{8}$ $[1]^{4}$ $[5/4]^{4}$ $[13/8]^{8}$ $[2]^{4}$ $[21/8]^{4}$ $[3]^{2}$
12	$[3/4]^{4}$ $[1]^{18}$ $[7/4]^{16}$ $[2]^{22}$ $[11/4]^{32}$ $[3]^{24}$ $[15/4]^{32}$ $[4]^{18}$ $[19/4]^{16}$ $[5]^{8}$
13	$[1]^{29}$ $[2]^{38}$ $[3]^{50}$ $[4]^{64}$ $[5]^{78}$ $[6]^{82}$ $[7]^{64}$ $[8]^{26}$ $[9]^{4}$

The resistance distances are shown in ascending order. $[a/b]^{n}$ denotes $n$ occurrences of the fraction $a/b$ .

2 Preliminary knowledge

In this paper, we only consider simple undirected graphs. For undefined notations and terminologies, see the book by Bondy and Murty [6].

A partition of a positive integer $t$ is a multiset of positive integers that sum to $t$ . We denote the number of partitions of $t$ by $p(t)$ . For example, since $\{5\},\{4,1\},\{3,2\},\{3,1,1\},\{2,2,1\},\{2,1,1,1\}$ , $\{1,1,1,1,1\}$ are all the partitions of $5$ , $p(5)=7$ .

Definition 2.1.

Let $A=\{a_{1},a_{2},\ldots,a_{p}\}$ and $B=\{b_{1},b_{2},\ldots,b_{q}\}$ be two different partitions of a positive integer $n$ . We say $A$ and $B$ are of equal sums of squares if

\sum_{i=1}^{p}a_{i}^{2}=\sum_{i=1}^{q}b_{i}^{2}.

Example 2.2.

$A:=\{3,3\},B:=\{4,1,1\}$ are of equal sums of squares.

Proposition 2.3.

Let $A$ and $B$ be two different partitions of a positive integer $n$ , where $A=\{a_{1},a_{2},\ldots,a_{p}\}$ and $B=\{b_{1},b_{2},\ldots,b_{q}\}$ . If $A$ and $B$ are of equal sums of squares, then

\sum_{1\leq i<j\leq p}a_{i}a_{j}=\sum_{1\leq i<j\leq q}b_{i}b_{j}.

Definition 2.4.

Let $G$ be a graph with $V(G)=\{g_{1},g_{2},\ldots,g_{n}\}$ . Let $S$ be a subset of $V(G)$ , where $S=\{g_{k_{1}},g_{k_{2}},\ldots,g_{k_{s}}\}$ , $1\leq s\leq n$ and $1\leq k_{1}<\cdots<k_{s}\leq n$ . Let $A=\{a_{1},a_{2},\ldots,a_{p}\}$ be a partition of a positive integer $t$ , where $p\leq s$ . Let $H_{1},H_{2},\ldots,H_{t}$ be $t$ graphs, where $V(H_{i})=\{h_{i,1},h_{i,2},\ldots,h_{i,n_{i}}\}$ for $i=1,2,\ldots,t$ . Let $\mathcal{H}=(H_{1},H_{2},\ldots,H_{t})$ and $T=\{h_{1,t_{1}},\ldots,h_{t,t_{t}}\}$ . The graph $G(S,A,\mathcal{H},T)$ is constructed from $G$ and $\mathcal{H}$ by identifying $g_{k_{1}},h_{1,t_{1}},h_{2,t_{2}},\ldots,h_{a_{1},t_{a_{1}}}$ , identifying $g_{k_{i}},h_{\sum_{j=1}^{i-1}a_{j}+1,t_{\sum_{j=1}^{i-1}a_{j}+1}},h_{\sum_{j=1}^{i-1}a_{j}+2,t_{\sum_{j=1}^{i-1}a_{j}+2}},\ldots$ , $h_{\sum_{j=1}^{i}a_{j},t_{\sum_{j=1}^{i}a_{j}}}$ , where $i=2,3,\ldots,p$ .

Example 2.5.

Let $G$ be a cycle of length 3 with vertex set $\{g_{1},g_{2},g_{3}\}$ , $S=\{g_{2},g_{3}\}$ and $A=\{3,3\}$ . Let $\mathcal{H}=(H_{1},H_{2},\ldots,H_{6})$ and $T=\{h_{1,1},h_{2,1},\ldots,h_{t,1}\}$ , where $H_{i}$ is a path of length $1$ with $V(H_{i})=\{h_{i,1},h_{i,2}\}$ for $i=1,2,\ldots,6$ . The graph $G(S,A,\mathcal{H},T)$ is depicted in Figure 2.

Figure 2:

G(S,A,\mathcal{H},T)

We denote by $\operatorname{RSV}(G,v)$ the multiset of the resistance distances between $v$ and other vertices of $G$ , that is, $\operatorname{RSV}(G,v)=\{R_{G}(v,u)\mid u\in V(G)\setminus\{v\}\}$ .

For two nonempty multisets $A$ and $B$ , both consisting of real numbers, we define the sum of $A$ and $B$ as the following multiset:

A+B=\{a+b\mid a\in A,b\in B\}.

Lemma 2.6.

[1] Let $x$ be a cut vertex of a connected graph $G$ . Let $u$ and $v$ be two vertices belonging to different components after $x$ is deleted from $G$ . Then $R_{G}(u,v)=R_{G}(u,x)+R_{G}(x,v)$ .

Proposition 2.7.

Let $G_{1},G_{2},H_{1}$ and $H_{2}$ be four graphs. Let $V(G_{i})=\{g_{i,1},\ldots,g_{i,n}\}$ , $V(H_{i})=\{h_{i,1},\ldots$ , $h_{i,m}\}$ , $S_{i}=\{g_{i,1}\}$ , $T_{i}=\{h_{i,1}\}$ , $\mathcal{H}_{i}=(H_{i})$ , where $i=1,2$ , and $A=\{1\}$ . Let $G=G_{1}(S_{1},A,\mathcal{H}_{1},T_{1})$ and $H=G_{2}(S_{2},A,\mathcal{H}_{2},T_{2})$ . If $\operatorname{RS}(G_{1})=\operatorname{RS}(G_{2})$ , $\operatorname{RSV}(G_{1},g_{1,1})=\operatorname{RSV}(G_{2},g_{2,1})$ , $\operatorname{RS}(H_{1})=\operatorname{RS}(H_{2})$ and $\operatorname{RSV}(H_{1},h_{1,1})=\operatorname{RSV}(H_{2},h_{2,1})$ , then $\operatorname{RSV}(G,g_{1,1})=\operatorname{RSV}(H,g_{2,1})$ and $\operatorname{RS}(G)=\operatorname{RS}(H)$ .

Proof.

By Lemma 2.6, we have

	$\displaystyle\operatorname{RS}(G)=\operatorname{RS}(G_{1})\cup\operatorname{RS}(H_{1})\cup(\operatorname{RSV}(G_{1},g_{1,1})+\operatorname{RSV}(H_{1},h_{1,1})),$
	$\displaystyle\operatorname{RS}(H)=\operatorname{RS}(G_{2})\cup\operatorname{RS}(H_{2})\cup(\operatorname{RSV}(G_{2},g_{2,1})+\operatorname{RSV}(H_{2},h_{2,1})),$
	$\displaystyle\operatorname{RSV}(G,g_{1,1})=\operatorname{RSV}(G_{1},g_{1,1})\cup\operatorname{RSV}(H_{1},h_{1,1})$

and

\operatorname{RSV}(H,g_{2,1})=\operatorname{RSV}(G_{2},g_{2,1})\cup\operatorname{RSV}(H_{2},h_{2,1}).

The results can be reached by a simple examination.

For two graphs $G$ and $H$ , if $\operatorname{RS}(G)=\operatorname{RS}(H)$ and there is a vertex $g$ of $G$ and a vertex $h$ of $H$ , such that $\operatorname{RSV}(G,g)=\operatorname{RSV}(H,h)$ , then we say that $G$ and $H$ hold relation $\mathcal{U}$ with respect to vertices $g$ and $h$ , denoted by $G$ - $g$ - $\mathcal{U}$ - $h$ - $H$ . Sometimes, we say that $G$ holds relation $\mathcal{U}$ with $H$ instead for simplicity while $G$ - $g$ - $\mathcal{U}$ - $h$ - $H$ is abbreviated as $G\mathcal{U}H$ .

Example 2.8.

If $T_{1}$ and $T_{2}$ are two graphs of $9$ verteices as shown in Figure 3, then $T_{1}$ holds relation $\mathcal{U}$ with $T_{2}$ .

By a simple calculation, $\operatorname{RS}(T_{1})=\operatorname{RS}(T_{2})=\{[5]^{1},[4]^{3},[\frac{15}{4}]^{2},[3]^{5},[\frac{11}{4}]^{4},[2]^{6},[\frac{7}{4}]^{4},[1]^{7},[\frac{3}{4}]^{4}\}$ and
$\operatorname{RSV}(T_{1},t_{1,3})=\operatorname{RSV}(T_{2},t_{2,3})=\{\frac{15}{4},\frac{11}{4},\frac{11}{4},\frac{7}{4},\frac{7}{4},1,\frac{3}{4},\frac{3}{4}\}$ .

(a)

T_{1}

(b)

T_{2}

Figure 3: Two graphs

T_{1}

and

T_{2}

holding the relation

\mathcal{U}

Proposition 2.9.

Let $G$ be a graph with vertex set $\{g_{1},g_{2},\ldots,g_{n}\}$ , and $S=\{g_{k_{1}},g_{k_{2}},\ldots,g_{k_{s}}\}$ , where $1\leq s\leq n$ and $1\leq k_{1}<\cdots<k_{s}\leq n$ . Let $F_{1},F_{2},\ldots,F_{t},H_{1},H_{2},\ldots,H_{t}$ be graphs with $F_{i}$ - $f_{i,1}$ - $\mathcal{U}$ - $h_{i,1}$ - $H_{i}$ , $f_{i,1}\in V(F_{i})$ and $h_{i,1}\in V(H_{i})$ for $i=1,2,\ldots,t$ . Let $\mathcal{F}=(F_{1},F_{2},\ldots,F_{t})$ , $\mathcal{H}=(H_{1},H_{2},\ldots,H_{t})$ , $T_{1}=\{f_{1,1},\ldots,f_{t,1}\}$ and $T_{2}=\{h_{1,1},\ldots,h_{t,1}\}$ . Let $A$ be a partition of positive integer $t$ , where $A=\{a_{1},a_{2},\ldots,a_{p}\}$ , $1\leq p\leq s\leq n$ . Then $G(S,A,\mathcal{F},T_{1})$ and $G(S,A,\mathcal{H},T_{2})$ have the same resistance spectrum.

Proof.

Since $F_{1},F_{2},\ldots,F_{t},H_{1},H_{2},\ldots,H_{t}$ be graphs with $F_{i}$ - $f_{i,1}$ - $\mathcal{U}$ - $h_{i,1}$ - $H_{i}$ for $i=1,2,\ldots,t$ , we have $\operatorname{RS}(H_{i})=\operatorname{RS}(F_{i}),i=1,2,\ldots,t$ , and $\operatorname{RSV}(H_{i},h_{i,1})=\operatorname{RSV}(F_{i},f_{i,1})$ . Then by Proposition 2.7, repeatedly, we have

\operatorname{RS}(G(S,A,\mathcal{F},T_{1}))=\operatorname{RS}(G(S,A,\mathcal{H},T_{2})).

Theorem 2.10.

For any positive integer $k$ , there exist at least $2^{k}$ graphs with the same resistance spectrum.

Proof.

Let $L_{k}$ denote the set of all $k$ -dimensional row vectors consisting of elements $1$ or $2$ . Clearly, $|L_{k}|=2^{k}$ . Let $T_{1}$ and $T_{2}$ be defined as in Example 2.8. Let $G_{k,p,q}=u_{1}u_{2}\cdots u_{p}v_{1}v_{2}\cdots v_{k}w_{1}w_{2}\cdots w_{q}$ be a path of length $k+p+q-1$ , where $q\geq p+1\geq 8$ . Let $S=\{v_{1},v_{2},\ldots,v_{k}\}$ and $A=\{[1]^{k}\}$ . For any element $I$ in $L_{k}$ , let $I=(I_{1},I_{2},\ldots,I_{k})$ , $\mathcal{H_{I}}=(H_{1},H_{2},\ldots,H_{k})$ , where $H_{i}$ is isomorphic to $T_{I_{i}}$ and the vertex $h_{i,1}$ is identical to $T_{I_{i},3}$ under some isomorphism $\theta$ between $H_{i}$ and $T_{I_{i}}$ . Let $T=\{h_{1,1},h_{2,1},\ldots,h_{t,1}\}$ and $G_{k,p,q}^{I}=G_{k,p,q}(S,A,\mathcal{H_{I}},T)$ . When $k=2,p=7,q=8$ and $I=(1,2)$ , $G_{k,p,q}^{I}$ is shown in Figure 4. Note that $G_{k,p,q}^{I}$ has a unique longest path of length $k+p+q-1$ . It follows easily that $G_{k,p,q}^{I}$ and $G_{k,p,q}^{J}$ are not isomorphic for any two different elements $I$ and $J$ of $L_{k}$ . By Proposition 2.9, $G_{k,p,q}^{I}$ and $G_{k,p,q}^{J}$ have the same resistance spectrum. Therefore, we can find $2^{k}$ graphs with the same resistance spectrum.

Figure 4:

G_{2,7,8}^{I}

Definition 2.11 ( $S$ -resistance transitive).

Let $G$ be a graph with vertex set $\{g_{1},g_{2},\ldots,g_{n}\}$ . Let $S=\{g_{k_{1}},g_{k_{2}},\ldots,g_{k_{s}}\}$ and $T=V(G)\setminus S$ , where $3\leq s\leq n$ and $1\leq k_{1}<\cdots<k_{s}\leq n$ .

Then $G$ is $S$ -resistance transitive if the following properties are satisfied:
(1) Let $u$ and $v$ be any two vertices in $S$ . If $T$ is not an empty set, then for each vertex $x$ in $T$ , $R_{G}(x,u)=R_{G}(x,v)$ .
(2) For each pair of different vertices $u$ and $v$ in $S$ , the resistance distance between them equal to the same value.

Example 2.12.

Let $G$ be a complete graph $K_{4}$ , $G^{\prime}$ an empty graph $\overline{K_{4}}$ , $V(G)=\{g_{1},g_{2},g_{3},g_{4}\}$ and $V(G^{\prime})=\{g_{1}^{\prime},g_{2}^{\prime},g_{3}^{\prime},g_{4}^{\prime}\}$ . Let $S=\{g_{1},g_{2},g_{3}\},T=\{g_{4}\},S^{\prime}=\{g_{1}^{\prime},g_{2}^{\prime},g_{3}^{\prime}\},T^{\prime}=\{g_{4}^{\prime}\}$ . Clearly, $R(g_{i},g_{j})=\frac{1}{2}$ and $R(g_{i}^{\prime},g_{j}^{\prime})=+\infty$ for $1\leq i\neq j\leq 4$ . Thus, $G$ and $G^{\prime}$ are $S$ -resistance transitive and $S^{\prime}$ -resistance transitive, respectively.

3 Main results

Lemma 3.1.

Let $G$ be a $S$ -resistance transitive graph with $V(G)=\{g_{1},g_{2},\ldots,g_{n_{1}}\}$ , $S=\{g_{1},g_{2},\ldots,g_{s}\}$ and $T=\{g_{s+1},g_{s+2},\ldots,g_{n_{1}}\}$ . There exists a constant $c$ such that for any two vertices $s_{1}\neq s_{2}\in S,$ $R_{G}(s_{1},s_{2})=c$ . Let $H_{1},H_{2},\ldots,H_{t}$ be $t$ graphs with $V(H_{i})=\{h_{i,1},h_{i,2},\ldots,h_{i,n_{i}}\}$ and $H_{i}\mathcal{U}H_{j}$ for $i,j\in\{1,2,\ldots,t\}$ . Assume $\operatorname{RSV}(H_{i},h_{i,1})=\operatorname{RSV}(H_{j},h_{j,1})$ . Let $\mathcal{H}=(H_{1},H_{2},\ldots,H_{t})$ and $T_{1}=\{h_{1,1},h_{2,1},\ldots,h_{t,1}\}$ . Let $A=\{a_{1},a_{2},\ldots,a_{p}\}$ be a partition of a positive integer $t,$ where $p\leq s$ .

Then the resistance spectrum of $G(S,A,\mathcal{H},T_{1})$ is

	$\displaystyle\operatorname{RS}(G)\bigcup t\cdot\operatorname{RS}(H_{1})$	$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+\operatorname{RSV}(H_{1},h_{1,1})]^{\sum_{i=1}^{p}\frac{a_{i}(a_{i}-1)}{2}}\}$
		$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+\operatorname{RSV}(H_{1},h_{1,1})+c]^{\sum_{1\leq i<j\leq p}a_{i}a_{j}}\}$
		$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+c]^{ts-t}\}\bigcup\left\{\left[R_{G}(g_{i},g_{1})+\operatorname{RSV}(H_{1},h_{1,1})\right]^{t}\mid i=s+1,\ldots,n\right\}.$

Proof.

The proof is obvious.

Theorem 3.2.

Let $G$ be a $S$ -resistance transitive graph with $V(G)=\{g_{1},g_{2},\ldots,g_{n_{1}}\}$ , $S=\{g_{1},g_{2},\ldots,g_{s}\}$ and $T=\{g_{s+1},g_{s+2},\ldots,g_{n_{1}}\}$ . There exists a constant $c$ such that for any two vertices $s_{1}\neq s_{2}\in S,$ $R_{G}(s_{1},s_{2})=c.$ Let $H_{1},H_{2},\ldots,H_{t}$ be $t$ graphs with $V(H_{i})=\{h_{i,1},h_{i,2},\ldots,h_{i,n_{i}}\}$ and $H_{i}\mathcal{U}H_{j}$ for $i,j\in\{1,2,\ldots,t\}$ . Assume $\operatorname{RSV}(H_{i},h_{i,1})=\operatorname{RSV}(H_{j},h_{j,1})$ . Let $\mathcal{H}=(H_{1},H_{2},\ldots,H_{t})$ and $T_{1}=\{h_{1,1},h_{2,1},\ldots$ ,
$h_{t,1}\}$ . Let $A=\{a_{1},a_{2},\ldots,a_{p}\}$ and $B=\{b_{1},b_{2},\ldots,b_{q}\}$ be two partitions of a positive integer $t$ , where $p,q\leq s$ . If $A$ and $B$ are of equal sums of squares, then graphs $G(S,A,\mathcal{H},T_{1})$ and $G(S,B,\mathcal{H},T_{1})$ have the same resistance spectrum.

Proof.

By Lemma 3.1, we have the resistance spectrum of $G(S,A,\mathcal{H},T_{1})$ is

	$\displaystyle\operatorname{RS}(G)\bigcup t\cdot\operatorname{RS}(H_{1})$	$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+\operatorname{RSV}(H_{1},h_{1,1})]^{\sum_{i=1}^{p}\frac{a_{i}(a_{i}-1)}{2}}\}$
		$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+\operatorname{RSV}(H_{1},h_{1,1})+c]^{\sum_{1\leq i<j\leq p}a_{i}a_{j}}\}$
		$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+c]^{ts-t}\}\bigcup\left\{\left[R_{G}(g_{i},g_{1})+\operatorname{RSV}(H_{1},h_{1,1})\right]^{t}\mid i=s+1,\ldots,n\right\}.$

and the resistance spectrum of $G(S,B,\mathcal{H},T_{1})$ is

	$\displaystyle\operatorname{RS}(G)\bigcup t\cdot\operatorname{RS}(H_{1})$	$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+\operatorname{RSV}(H_{1},h_{1,1})]^{\sum_{i=1}^{q}\frac{b_{i}(b_{i}-1)}{2}}\}$
		$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+\operatorname{RSV}(H_{1},h_{1,1})+c]^{\sum_{1\leq i<j\leq q}b_{i}b_{j}}\}$
		$\displaystyle\bigcup\{[\operatorname{RSV}(H_{1},h_{1,1})+c]^{ts-t}\}\bigcup\left\{\left[R_{G}(g_{i},g_{1})+\operatorname{RSV}(H_{1},h_{1,1})\right]^{t}\mid i=s+1,\ldots,n\right\}.$

Since $A$ and $B$ are of equal sums of squares, we have

\sum_{i=1}^{p}\frac{a_{i}(a_{i}-1)}{2}={\sum_{i=1}^{q}\frac{b_{i}(b_{i}-1)}{2}}

and

\sum_{1\leq i<j\leq p}a_{i}a_{j}={\sum_{1\leq i<j\leq q}b_{i}b_{j}}.

Thus graphs $G(S,A,\mathcal{H},T_{1})$ and $G(S,B,\mathcal{H},T_{1})$ have the same resistance spectrum.

Example 3.3.

Let $\mathcal{H}=(H_{1},H_{2},\ldots,H_{6})$ , where $H_{i}$ is a path of length $1$ with $V(H_{i})=\{h_{i,1},h_{i,2}\}$ for $i=1,2,\ldots,6$ . Let $T=\{h_{1,1},h_{2,1},\ldots,h_{6,1}\}$ , $A_{1}=\{3,3\},A_{2}=\{4,1,1\}$ . $A_{1}$ and $A_{2}$ are of equal sums of squares. Let $S_{1}=\overline{K_{3}}$ and $S_{2}=K_{3}$ . Clearly, $S_{1}$ and $S_{2}$ are $V(S_{1})$ -resistance transitive and $V(S_{2})$ -resistance transitive, respectively. Consequently, the graphs $S_{1}(V(S_{1}),A_{1},\mathcal{H},T)$ and $S_{1}(V(S_{1}),A_{2},\mathcal{H},T)$ have the same resistance spectrum, as shown in Pair 1 of Figure 1; the graphs $S_{2}(V(S_{2}),A_{1},\mathcal{H},T)$ and $S_{2}(V(S_{2}),A_{2},\mathcal{H},T)$ have the same resistance spectrum, as depicted in Pair 2 of Figure 1.

Proposition 3.4.

Let $G$ be any graph of order $n$ , $X$ be a subset of $V(G)$ , and $S$ be a complete graph $K_{r}$ or an empty graph $\overline{K_{r}}$ . $H$ is obtained from $G$ and $S$ by join every vertex of $X$ to every vertex of $S$ . Then $H$ is $V(S)$ -resistance transitive graph.

Proof.

The proof is obvious and omitted.

Theorem 3.5.

If $n\geq 10$ , then there are at least $2(n-9)p(n-9)$ pairs of graphs of order $n$ with the same resistance spectrum, where $p(n-9)$ is the number of partitions of the integer $n-9$ .

Proof.

Set $t=n-9$ . Let $C_{1},C_{2},\ldots,C_{p(t)}$ be all partitions of $t$ with $C_{i}=\{c_{i,1},c_{i,2},\ldots,c_{i,q_{i}}\}$ , where $c_{i,1}\geq c_{i,2}\geq\cdots\geq c_{i,q_{i}}$ , let $G_{i}$ be a graph with $t$ vertices, where the vertex set is $\{g_{i,1},g_{i,2},\ldots,g_{i,t}\}$ , $i\in\{1,2,\ldots,p(t)\}$ . The edges of $G_{i}$ are defined as follows: The first $c_{i,1}$ vertices form a complete subgraph, then the next $c_{i,2}$ vertices form a complete subgraph, and so on, the last $c_{i,q_{i}}$ vertices form a complete subgraph finally. Let $X_{i,j}=\{g_{i,1},g_{i,2},\ldots,g_{i,j}\}$ , $S_{1}=K_{3}$ and $S_{2}=\overline{K_{3}}$ . Let $Q_{i,j,k}$ be a graph obtained from $G_{i}$ and $S_{k}$ by join every vertex of $X_{i,j}$ to every vertex of $S_{k}$ , where $i\in\{1,2,\ldots,p(t)\}$ , $j\in\{1,2,\ldots,t\}$ and $k\in\{1,2\}$ . Thus, by Proposition 3.4, $Q_{i,j,k}$ is $V(S_{k})$ -resistance transitive graph.

Let $\mathcal{H}=(H_{1},H_{2},\ldots,H_{6})$ , where $H_{i}$ is a path of length $1$ with $V(H_{i})=\{h_{i,1},h_{i,2}\}$ for $i=1,2,\ldots,6$ . Let $T=\{h_{1,1},h_{2,1},\ldots,h_{6,1}\}$ . $A_{1}:=\{3,3\}$ and $A_{2}:=\{4,1,1\}$ are two different partitions of a positive integer $6$ , since $A_{1}$ and $A_{2}$ are of equal sums of squares, by Theorem 3.2, graphs $Q_{i,j,k}(V(S_{k}),A_{1},\mathcal{H},T)$ and $Q_{i,j,k}(V(S_{k}),A_{2},\mathcal{H},T)$ have the same resistance spectrum. Note that there exists a unique connected component $Q$ in $Q_{i,j,k}(V(S_{k}),A_{l},\mathcal{H},T)$ satisfying the conditions: $Q$ contains at least $6$ vertices with degree $1$ , and there exist three vertices with degree $1$ in $Q$ that share a common neighbor. It follows easily that $Q_{i_{1},j_{1},k_{1}}(V(S_{k_{1}}),A_{l_{1}},\mathcal{H},T)$ and $Q_{i_{2},j_{2},k_{2}}(V(S_{k_{2}}),A_{l_{2}},\mathcal{H},T)$ are not isomorphic if $i_{1}=i_{2}$ , $j_{1}=j_{2}$ , $k_{1}=k_{2}$ , and $l_{1}=l_{2}$ are not all simultaneously satisfied.

According to the multiplication principle, there are at least $2tp(t)$ pair graphs with the same resistance spectrum. Therefore, when $n\geq 10$ , there are at least $2\cdot(n-9)p(n-9)$ pairs of graphs with the same resistance spectrum.

Example 3.6.

There exist $8$ pairs of graphs of order $11$ with the same resistance spectrum, as shown in Figures 6–12. Here $Q_{i,j,k,l}=Q_{i,j,k}(V(S_{k}),A_{l},\mathcal{H},T)$ , where $Q_{i,j,k}(V(S_{k}),A_{l},\mathcal{H},T)$ is defined as in Theorem 3.5 for $i,j,k,l\in\{1,2\}$ .

(a)

Q_{1,1,1,1}

(b)

Q_{1,1,1,2}

Figure 5:

Q_{1,1,1,1}

and

Q_{1,1,1,2}

(c)

Q_{1,2,1,1}

(d)

Q_{1,2,1,2}

Figure 6:

Q_{1,2,1,1}

and

Q_{1,2,1,2}

(a)

Q_{1,1,2,1}

(b)

Q_{1,1,2,2}

Figure 7:

Q_{1,1,2,1}

and

Q_{1,1,2,2}

(c)

Q_{1,2,2,1}

(d)

Q_{1,2,2,2}

Figure 8:

Q_{1,2,2,1}

and

Q_{1,2,2,2}

(a)

Q_{2,1,1,1}

(b)

Q_{2,1,1,2}

Figure 9:

Q_{2,1,1,1}

and

Q_{2,1,1,2}

(c)

Q_{2,2,1,1}

(d)

Q_{2,2,1,2}

Figure 10:

Q_{2,2,1,1}

and

Q_{2,2,1,2}

(a)

Q_{2,1,2,1}

(b)

Q_{2,1,2,2}

Figure 11:

Q_{2,1,2,1}

and

Q_{2,1,2,2}

(c)

Q_{2,2,2,1}

(d)

Q_{2,2,2,2}

Figure 12:

Q_{2,2,2,1}

and

Q_{2,2,2,2}

4 Conclusion

In this paper, we propose a method for constructing graphs with the same resistance spectrum. We also present a lower bound for the number of pairs of graphs which have the same resistance spectrum among graphs with $n(\geq 10)$ vertices. Our method is derived from observing pairs 1 and 2 in Figure 1. By carefully examining the other pairs of graphs in Figure 1, it is possible to find more methods for construting non-isomorphic graphs with the same resistance spectrum.

References

[1] D. J. Klein, M. Randić, Resistance distance, J. Math. Chem. 12 (1) (1993) 81–95.
[2] L. Baxter, Counterexamples wanted–graph isomorphism & resistances, sci.math.research (Apr. 22, 1999).
[3] L. Baxter, Counterexample wanted for graph isomorphism conjecture, USENET: comp.theory (Apr. 26, 1999).
[4] J. Rickard, Counterexample wanted for graph isomorphism conjecture, USENET: comp.theory (Apr. 23, 1999).
[5] E. W. Weisstein, Resistance-equivalent graphs, mathworld—a wolfram web resource (Feb. 19, 2021).
[6] J. A. Bondy, U. S. R. Murty, Graph theory, Grad. Texts In Math. 244, Springer-Verlag, New York, 2008.

A method for constructing graphs with the same resistance spectrum

Abstract

keywords:

MSC:

1 Introduction

2 Preliminary knowledge

Definition 2.1.

Example 2.2.

Proposition 2.3.

Definition 2.4.

Example 2.5.

Lemma 2.6.

Proposition 2.7.

Proof.

Example 2.8.

Proposition 2.9.

Proof.

Theorem 2.10.

Proof.

Definition 2.11 (SS-resistance transitive).

Example 2.12.

3 Main results

Lemma 3.1.

Proof.

Theorem 3.2.

Proof.

Example 3.3.

Proposition 3.4.

Proof.

Theorem 3.5.

Proof.

Example 3.6.

4 Conclusion

References

Definition 2.11 ( $S$ -resistance transitive).