Proof of a conjecture on spectral distance between cycles, paths and certain trees

Abstract

We confirm the following conjecture which has been proposed by Stanić in [I. Jovanović and Z. Stanić, Spectral distances of graphs, Linear Algebra Appl. 436(5) (2012) 1425-1435]: 0.945≈limn→∞σ(Pn,Zn) =limn→∞σ(Wn,Zn) = 1 2limn→∞σ(Pn,Wn),limn→∞σ(C2n,Z2n) = 2, where σ(G1,G2) =∑i=1n|λ i(G1)-λi(G2)| is the spectral distance between n vertex non-isomorphic graphs G1 and G2 with adjacency spectra λ1(Gi) ≥ λ2(Gi) ≥⋯ ≥ λn(Gi) for i = 1, 2, and Pn and Cn denote the path and cycle on n vertices, respectively, Zn denotes the coalescence of Pn-2 and P3 on one of the vertices of degree 1 of Pn-2 and the vertex of degree 2 of P3, and Wn denotes the coalescence of Zn-2 and P3 on the vertex of degree 1 of Zn-2 which is adjacent to a vertex of degree 2 and the vertex of degree 2 of P3. © 2021 World Scientific Publishing Company.