




















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$ be two nonisomorphic graphs on $n$ vertices with spectra $$λ_1 \geq λ_2 \geq \cdots \geq λ_n \;\;\;\text{and}\;\;\; λ'_1 \geq λ'_2 \geq \cdots \geq λ'_n,$$ respectively. Define the distance between the spectra of $G_n$ and $G'_n$ as $$λ(G_n,G'_n) =\sum_{i=1}^n (λ_i-λ'_i)^2 \;\;\; \big(\text{or use}\; \sum_{i=1}^n|λ_i-λ'_i|\big).$$ %Let $ε$ be a nonnegative number. Graphs $G_n$ and $G'_n$ are $ε$-cospectral if $λ(G_n,G'_n)\leq ε$. Thus, $G_n$ %and $G'_n$ are $0$-cospectral if and only if $G_n$ and $G'_n$ are cospectral. Define the cospectrality of $G_n$ by $$\text{cs}(G_n) = \min\{λ(G_n,G'_n) \;:\; G'_n \;\;\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. $σ(G_n,G'_n)=\sum_{i=1}^n|λ_i-λ'_i|$. We find $\text{cs}(K_n)$, $\text{cs}(nK_1)$, $\text{cs}(K_2+(n-2)K_1)$ ($n\geq 2$), $\text{cs}(K_{n,n})$ and $\text{cs}(K_{n,n+1})$, where $K_n, nK_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\geq 2$), and the complete bipartite graph with parts of sizes $n$ and $m$, respectively.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。