A Conjecture about spectral distances between cycles, paths and certain trees

Alireza Abdollahi Department of Pure Mathematics, Faculty of Mathematics and Statistics, University of Isfahan, Isfahan 81746-73441, Iran; and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran [email protected] and Niloufar Zakeri Department of Pure Mathematics, Faculty of Mathematics and Statistics, University of Isfahan, Isfahan 81746-73441, Iran [email protected]

Abstract.

We confirm the following conjecture which has been proposed in [Linear Algebra and its Applications, 436 (2012), No. 5, 1425-1435.]:

0.945\approx\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\displaystyle\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n})=\frac{1}{2}\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},W_{n});\ \displaystyle\lim_{n\longrightarrow\infty}\sigma(C_{2n},Z_{2n})=2,

where $\sigma(G_{1},G_{2})=\sum_{i=1}^{n}|\lambda_{i}(G_{1})-\lambda_{i}(G_{2})|$ is the spectral distance between $n$ vertex non-isomorphic graphs $G_{1}$ and $G_{2}$ with adjacency spectra $\lambda_{1}(G_{i})\geq\lambda_{2}(G_{i})\geq\cdots\geq\lambda_{n}(G_{i})$ for $i=1,2$ , and $P_{n}$ and $C_{n}$ denote the path and cycle on $n$ vertices, respectively; $Z_{n}$ denotes the coalescence of $P_{n-2}$ and $P_{3}$ on one of the vertices of degree 1 of $P_{n-2}$ and the vertex of degree $2$ of $P_{3}$ ; and $W_{n}$ denotes the coalescence of $Z_{n-2}$ and $P_{3}$ on the vertex of degree 1 of $Z_{n-2}$ which is adjacent to a vertex of degree $2$ and the vertex of degree $2$ of $P_{3}$ .

Key words and phrases:

Adjacency spectra of graphs; Spectral distance of graphs; Path; Cycle

2010 Mathematics Subject Classification:

05C50; 05C31

1. Introduction and Results

All graphs considered here are simple, that is finite and undirected without loops and multiple edges. By the eigenvalues of $G$ , we mean those of its adjacency matrix.

In [4], the following conjecture has been proposed:

0.945\approx\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\displaystyle\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n})=\frac{1}{2}\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},W_{n});\ \displaystyle\lim_{n\longrightarrow\infty}\sigma(C_{2n},Z_{2n})=2,

Let us first introduce some notations.

The coalescence of two graphs $G$ and $H$ is obtained by identifying a vertex $u$ of $G$ with a vertex $v$ of $H$ ; $Z_{n}$ denotes the coalescence of $P_{n-2}$ and $P_{3}$ on one of the vertices of degree 1 of $P_{n-2}$ and the vertex of degree $2$ of $P_{3}$ ; and $W_{n}$ denotes the coalescence of $Z_{n-2}$ and $P_{3}$ on the vertex of degree 1 of $Z_{n-2}$ which is adjacent to a vertex of degree $2$ and the vertex of degree $2$ of $P_{3}$ . They are depicted in Figure 1 (Their spectra can be found in [2], p. 77).

Our main result is as follows.

Theorem 1.1.

(1)

$\displaystyle\lim_{n\longrightarrow\infty}\sigma(C_{2n},Z_{2n})=2.$
(2)

$\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.$
(3)

$\displaystyle\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.$
(4)

$\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\displaystyle\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n})=\frac{1}{2}\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},W_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.$

Refer to caption — Figure 1. Graphs $Z_{n}$ and $W_{n}$ .

2. Proof of the conjecture

To prove the following results, we need the Table 1.

Graph	Eigenvalues
$P_{n}$	$2\cos(\frac{k\pi}{n+1}),k=1,\ldots,n$
$C_{n}$	$2\cos(\frac{2k\pi}{n}),k=1,\ldots,n$
$Z_{n}$	$0,2\cos(\frac{(2k-1)\pi}{2n-2}),k=1,\ldots,n-1$
$W_{n}$	$2,0,0,-2,2\cos(\frac{k\pi}{n-3}),k=1,\ldots,n-4$

Table 1. Some specific graphs and their spectra

Proof of Theorem 1.1.

(1)

Let $n\geq 2$ . By Table 1,

\lambda_{1}(C_{2n})>\lambda_{k}(C_{2n})=\lambda_{k+1}(C_{2n})>\lambda_{k+2}(C_{2n})=\lambda_{k+3}(C_{2n})>\lambda_{2n}(C_{2n}),\ \ k=2,4,6,\ldots,2n-4.

Assume that $n$ is odd. We have

\lambda_{k}(C_{2n})>\lambda_{k}(Z_{2n})>\lambda_{k+1}(Z_{2n})>\lambda_{k+1}(C_{2n}),\ \ k=1,3,5,\ldots,2n-1.

If $n$ is even, then $\lambda_{k}(C_{2n})=\lambda_{k}(Z_{2n})$ for $k=n,n+1$ and the other eigenvalues are the same as the case that $n$ is odd.

Since $C_{2n}$ and $Z_{2n}$ are bipartite, by using the above (in)equalities, we have

$\displaystyle\sigma(C_{2n},Z_{2n})$	$\displaystyle=$	$\displaystyle 2(\lambda_{1}(C_{2n})-\lambda_{1}(Z_{2n}))+\displaystyle\sum_{k=2}^{2n-1}\|\lambda_{k}(C_{2n})-\lambda_{k}(Z_{2n})\|$
	$\displaystyle=$	$\displaystyle 2(\lambda_{1}(C_{2n})-\lambda_{1}(Z_{2n}))+\displaystyle\sum_{{k=2}\;{\text{, $k$ is even}\;}}^{2n-2}\lambda_{k}(Z_{2n})-\lambda_{k}(C_{2n})+\lambda_{k+1}(C_{2n})-\lambda_{k+1}(Z_{2n})$
	$\displaystyle=$	$\displaystyle 2(\lambda_{1}(C_{2n})-\lambda_{1}(Z_{2n}))+2\displaystyle\sum_{k=2}^{n-1}(-1)^{k}\lambda_{k}(Z_{2n})$
	$\displaystyle=$	$\displaystyle 2\lambda_{1}(C_{2n})+2\displaystyle\sum_{k=1}^{n-1}(-1)^{k}\lambda_{k}(Z_{2n})$
	$\displaystyle=$	$\displaystyle 4+4\displaystyle\sum_{k=1}^{n-1}(-1)^{k}\cos(\frac{(2k-1)\pi}{4n-2}).$

Since $\displaystyle\lim_{n\rightarrow\infty}\displaystyle\sum_{k=1}^{n-1}(-1)^{k}\cos(\frac{(2k-1)\pi}{4n-2})=\frac{-1}{2},$ we have

\lim_{n\rightarrow\infty}\sigma(C_{2n},Z_{2n})=2.

(2)

Let $n\geq 4$ and $a_{n}:=\sigma(P_{n},Z_{n})$ . We prove

\displaystyle\lim_{n\longrightarrow\infty}a_{4n+1}=\displaystyle\lim_{n\longrightarrow\infty}a_{4n+2}=\displaystyle\lim_{n\longrightarrow\infty}a_{4n+3}=\displaystyle\lim_{n\longrightarrow\infty}a_{4n}=\frac{8-8\sqrt{2}+2\pi}{\pi},

which follows that $a_{n}$ is convergent to $\frac{8-8\sqrt{2}+2\pi}{\pi}$ .

Suppose that $\lambda_{1}(P_{n})\geq\cdots\geq\lambda_{n}(P_{n})$ and $\lambda_{1}(Z_{n})\geq\cdots\geq\lambda_{n}(Z_{n})$ are the eigenvalues of $P_{n}$ and $Z_{n}$ , respectively. If $n\equiv 1\pmod{4}$ , then

\lambda_{k}(Z_{n})>\lambda_{k}(P_{n}),\ \ \ k=1,\ldots,\frac{n-1}{4},

\lambda_{k}(Z_{n})<\lambda_{k}(P_{n}),\ \ \ k=\frac{n+3}{4},\ldots,\frac{n-1}{2},

and

\lambda_{\frac{n+1}{2}}(Z_{n})=\lambda_{\frac{n+1}{2}}(P_{n}).

Thus, by Table 1 and the bipartiteness of $P_{n}$ and $Z_{n}$ , we have

	$\displaystyle\sigma(P_{n},Z_{n})$	$\displaystyle=$	$\displaystyle 2\big{(}\displaystyle\sum_{k=1}^{\frac{n-1}{4}}(\lambda_{k}(Z_{n})-\lambda_{k}(P_{n}))+\displaystyle\sum_{k=\frac{n+3}{4}}^{\frac{n-1}{2}}(\lambda_{k}(P_{n})-\lambda_{k}(Z_{n}))\big{)}$
		$\displaystyle=$	$\displaystyle 4\big{(}\displaystyle\sum_{k=1}^{\frac{n-1}{4}}(\cos(\frac{(2k-1)\pi}{2n-2})-\cos(\frac{k\pi}{n+1}))+\displaystyle\sum_{k=\frac{n+3}{4}}^{\frac{n-1}{2}}(\cos(\frac{k\pi}{n+1})-\cos(\frac{(2k-1)\pi}{2n-2}))\big{)}.$

By using a simple code (e.g., see 2) in symbolic computational software Maple [7], we have

\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.

If $n\equiv 3\pmod{4}$ , then

\lambda_{k}(Z_{n})>\lambda_{k}(P_{n}),\ \ \ k=1,\ldots,\frac{n-3}{4},

\lambda_{k}(Z_{n})<\lambda_{k}(P_{n}),\ \ \ k=\frac{n+5}{4},\ldots,\frac{n-1}{2},

and

\lambda_{k}(Z_{n})=\lambda_{k}(P_{n}),\ \ \ k=\frac{n+1}{4},\frac{n+1}{2}.

It follows from Table 1 and the bipartiteness of $P_{n}$ and $Z_{n}$ that

	$\displaystyle\sigma(P_{n},Z_{n})$	$\displaystyle=$	$\displaystyle 2\big{(}\displaystyle\sum_{k=1}^{\frac{n-3}{4}}(\lambda_{k}(Z_{n})-\lambda_{k}(P_{n}))+\displaystyle\sum_{k=\frac{n+5}{4}}^{\frac{n-1}{2}}(\lambda_{k}(P_{n})-\lambda_{k}(Z_{n}))\big{)}$
		$\displaystyle=$	$\displaystyle 4\big{(}\displaystyle\sum_{k=1}^{\frac{n-3}{4}}(\cos(\frac{(2k-1)\pi}{2n-2})-\cos(\frac{k\pi}{n+1}))+\displaystyle\sum_{k=\frac{n+5}{4}}^{\frac{n-1}{2}}(\cos(\frac{k\pi}{n+1})-\cos(\frac{(2k-1)\pi}{2n-2}))\big{)}.$

By using Maple [7],

\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.

n^{*}=\left\{\begin{array}[]{ll}\frac{n}{4}&n\equiv 0\pmod{4},\\ \\ \frac{n-2}{4}&n\equiv 2\pmod{4},\end{array}\right.

then

\lambda_{k}(Z_{n})>\lambda_{k}(P_{n}),\ \ \ k=1,\ldots,n^{*},

and

\lambda_{k}(Z_{n})<\lambda_{k}(P_{n}),\ \ \ k=n^{*}+1,\ldots,\frac{n}{2}.

Therefore

	$\displaystyle\sigma(P_{n},Z_{n})$	$\displaystyle=$	$\displaystyle 2\big{(}\displaystyle\sum_{k=1}^{n^{}}(\lambda_{k}(Z_{n})-\lambda_{k}(P_{n}))+\displaystyle\sum_{k=n^{}+1}^{\frac{n}{2}}(\lambda_{k}(P_{n})-\lambda_{k}(Z_{n}))\big{)}$
		$\displaystyle=$	$\displaystyle 4\big{(}\displaystyle\sum_{k=1}^{n^{}}(\cos(\frac{(2k-1)\pi}{2n-2})-\cos(\frac{k\pi}{n+1}))+\displaystyle\sum_{k=n^{}+1}^{\frac{n}{2}}(\cos(\frac{k\pi}{n+1})-\cos(\frac{(2k-1)\pi}{2n-2}))\big{)}.$

In both cases, by using Maple [7], we have

\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.

Therefore $a_{n}=\sigma(P_{n},Z_{n})$ is convergent to $\frac{8-8\sqrt{2}+2\pi}{\pi}$ .

(3)

Let $n\geq 6$ and $b_{n}:=\sigma(P_{n},Z_{n})$ . We prove

\displaystyle\lim_{n\longrightarrow\infty}b_{4n+1}=\displaystyle\lim_{n\longrightarrow\infty}b_{4n+2}=\displaystyle\lim_{n\longrightarrow\infty}b_{4n+3}=\displaystyle\lim_{n\longrightarrow\infty}b_{4n}=\frac{8-8\sqrt{2}+2\pi}{\pi},

which follows that $b_{n}$ is convergent to $\frac{8-8\sqrt{2}+2\pi}{\pi}$ .

Suppose that $\lambda_{1}(W_{n})\geq\cdots\geq\lambda_{n}(W_{n})$ and $\lambda_{1}(Z_{n})\geq\cdots\geq\lambda_{n}(Z_{n})$ are the eigenvalues of $W_{n}$ and $Z_{n}$ , respectively. By similar arguments given in part (2), if $n\equiv 1\pmod{4}$ , then

	$\displaystyle\sigma(W_{n},Z_{n})$	$\displaystyle=$	$\displaystyle 2\big{(}\displaystyle\sum_{k=1}^{\frac{n-1}{4}}(\lambda_{k}(W_{n})-\lambda_{k}(Z_{n}))+\displaystyle\sum_{k=\frac{n+3}{4}}^{\frac{n-1}{2}}(\lambda_{k}(Z_{n})-\lambda_{k}(W_{n}))\big{)}$
		$\displaystyle=$	$\displaystyle 4\big{(}\displaystyle\sum_{k=1}^{\frac{n-1}{4}}(\cos(\frac{(k-1)\pi}{n-3})-\cos(\frac{(2k-1)\pi}{2n-2}))+\displaystyle\sum_{k=\frac{n+3}{4}}^{\frac{n-1}{2}}(\cos(\frac{(2k-1)\pi}{2n-2})-\cos(\frac{(k-1)\pi}{n-3}))\big{)}.$

We have

	$\displaystyle\sigma(W_{n},Z_{n})$	$\displaystyle=$	$\displaystyle 2\big{(}\displaystyle\sum_{k=1}^{\frac{n-3}{4}}(\lambda_{k}(W_{n})-\lambda_{k}(Z_{n}))+\displaystyle\sum_{k=\frac{n+5}{4}}^{\frac{n-1}{2}}(\lambda_{k}(Z_{n})-\lambda_{k}(W_{n}))\big{)}$
		$\displaystyle=$	$\displaystyle 4\big{(}\displaystyle\sum_{k=1}^{\frac{n-1}{4}}(\cos(\frac{(k-1)\pi}{n-3})-\cos(\frac{(2k-1)\pi}{2n-2}))+\displaystyle\sum_{k=\frac{n+5}{4}}^{\frac{n-1}{2}}(\cos(\frac{(2k-1)\pi}{2n-2})-\cos(\frac{(k-1)\pi}{n-3}))\big{)}.$

where $n\equiv 3\pmod{4}$ . In both cases, by using Maple [7],

\displaystyle\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.

n^{*}=\left\{\begin{array}[]{ll}\frac{n}{4}&n\equiv 0\pmod{4},\\ \\ \frac{n-2}{4}&n\equiv 2\pmod{4},\end{array}\right.

then

\lambda_{k}(W_{n})>\lambda_{k}(Z_{n}),\ \ \ k=1,\ldots,n^{*},

\lambda_{k}(W_{n})<\lambda_{k}(Z_{n}),\ \ \ k=n^{*}+1,\ldots,\frac{n}{2}-1,

and

\lambda_{\frac{n}{2}}(W_{n})=\lambda_{\frac{n}{2}}(Z_{n}).

Therefore

	$\displaystyle\sigma(W_{n},Z_{n})$	$\displaystyle=$	$\displaystyle 2\big{(}\displaystyle\sum_{k=1}^{n^{}}(\lambda_{k}(W_{n})-\lambda_{k}(Z_{n}))+\displaystyle\sum_{k=n^{}+1}^{\frac{n}{2}-1}(\lambda_{k}(Z_{n})-\lambda_{k}(W_{n}))\big{)}$
		$\displaystyle=$	$\displaystyle 4\big{(}\displaystyle\sum_{k=1}^{n^{}}(\cos(\frac{(k-1)\pi}{n-3})-\cos(\frac{(2k-1)\pi}{2n-2}))+\displaystyle\sum_{k=n^{}+1}^{\frac{n}{2}-1}(\cos(\frac{(2k-1)\pi}{2n-2})-\cos(\frac{(k-1)\pi}{n-3}))\big{)}.$

In both cases, by using Maple [7],

\displaystyle\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.

Thus $b_{n}=\sigma(W_{n},Z_{n})$ is convergent to $\frac{8-8\sqrt{2}+2\pi}{\pi}$ .

(4)

The eigenvalues of $P_{n}$ and $W_{n}$ satisfy the same (in)equalities as the eigenvalues of $P_{n}$ and $Z_{n}$ . So, by the parts (2) and (3), we obtain

\sigma(P_{n},W_{n})=\sigma(P_{n},Z_{n})+\sigma(W_{n},Z_{n}).

Since

\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n}),

we have

\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},Z_{n})=\displaystyle\lim_{n\longrightarrow\infty}\sigma(W_{n},Z_{n})=\frac{1}{2}\displaystyle\lim_{n\longrightarrow\infty}\sigma(P_{n},W_{n})=\frac{8-8\sqrt{2}+2\pi}{\pi}\approx 0.945.

This completes the proof. $\hfill\Box$

Acknowledgments

The research of the first author was in part supported by a grant from School of Mathematics, Institute for Research in Fundamental Sciences (IPM).

References

[1] A. Abdollahi, Sh. Janbaz and M. R. Oboudi, Distance between spectra of graphs, Linear Algebra Appl., 466 (2015), 401–408.
[2] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, Academic Press, Inc., New York, 1980.
[3] K. Ch. Das and S. Sun, Distance between the normalized Laplacian spectra of two graphs, Linear Algebra Appl., 530 (2017), 305–321.
[4] I. Jovanović and Z. Stanić, Spectral distances of graphs, Linear Algebra Appl., 436 (2012), No. 5, 1425–1435.
[5] I. Jovanović and Z. Stanić, Spectral distances of graphs based on their different matrix representations, Filomat, 28 (2014), No. 4, 723–734.
[6] H. Lin, D. Li and K. Ch. Das, Distance between distance spectra of graphs, Linear Multilinear Algebra, 65 (2017), No. 12, 2538–2550.
[7] Maple, Computer Algebra System, Numeric Computation Waterloo Maple, www.maplesoft.com/products/maple/