${\ell }^1$-Cospectrality of graphs

Abstract

The following problem has been proposed in [Research problems from the Aveiro workshop on graph spectra, {\em Linear Algebra and its Applications}, {\bf 423} (2007) 172-181.]:\\ (Problem AWGS.4) Let $G_n$ and $G_n^{\prime }$ be two nonisomorphic graphs on $n$ vertices with spectra $${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n\text{and}{\lambda }_1^{\prime }\ge {\lambda }_2^{\prime }\ge \cdots \ge {\lambda }_n^{\prime },$$ respectively. Define the distance between the spectra of $G_n$ and $G_n^{\prime }$ as $$\lambda (G_n,G_n^{\prime })=\sum _{i=1}^n({\lambda }_i-{\lambda }_i^{\prime }{)}^2(\text{or use}\sum _{i=1}^n|{\lambda }_i-{\lambda }_i^{\prime }|).$$ %Let $\epsilon$ be a nonnegative number. Graphs $G_n$ and $G_n^{\prime }$ are $\epsilon$-cospectral if $\lambda (G_n,G_n^{\prime })\le \epsilon$. Thus, $G_n$ %and $G_n^{\prime }$ are $0$-cospectral if and only if $G_n$ and $G_n^{\prime }$ are cospectral. Define the cospectrality of $G_n$ by $$\text{cs}(G_n)=\min \{\lambda (G_n,G_n^{\prime }):G_n^{\prime }\text{not isomorphic to}{G}_n\}.$$ %Thus $\text{cs}(G_n)=0$ if and only if $G_n$ has a cospectral mate. %This function measures how far apart the spectrum of a graph with $n$ vertices can be from the %spectrum of any other graph with $n$ vertices.\\ {\bf Problem A.} Investigate $\text{cs}(G_n)$ for special classes of graphs. In this paper we study Problem A for certain graphs with respect to the ${\ell }^1$-norm, i.e. $\sigma (G_n,G_n^{\prime })={\sum }_{i=1}^n|{\lambda }_i-{\lambda }_i^{\prime }|$. We find $\text{cs}(K_n)$, $\text{cs}(n{K}_1)$, $\text{cs}(K_2+(n-2)K_1)$ ($n\ge 2$), $\text{cs}(K_{n,n})$ and $\text{cs}(K_{n,n+1})$, where $K_n,n{K}_1,K_2+(n-2)K_1,K_{n,m}$ denote the complete graph on $n$ vertices, the null graph on $n$ vertices, the disjoint union of the $K_2$ with $n-2$ isolated vertices ($n\ge 2$), and the complete bipartite graph with parts of sizes $n$ and $m$, respectively.

References in corpus (1)

• Spectral distances on graphs