Distance between spectra of graphs

Abstract

Richard Brualdi proposed in Stevanivić (2007) [10] the following problem: (Problem AWGS.4) Let Gn and Gn′ be two nonisomorphic graphs on n vertices with spectraλ1≥λ2≥âi»≥λnandλ1′≥λ2′≥âi»≥λn′, respectively. Define the distance between the spectra of Gn and Gn′ asλ(Gn,Gn′)=λi=1n(λi(or use λi=1n|λi-λi′|). Define the cospectrality of Gn bycs(Gn)=min{λ(Gn,Gn′):Gn′ not isomorphic to Gn}. Letcsn=max{cs(Gn):Gn a graph on n vertices}. Investigate cs(Gn) for special classes of graphs. Find a good upper bound on csn. In this paper we completely answer Problem B by proving that csn=2 for all n≥2, whenever csn is computed with respect to any â.,"p-norm with 1lt∞ and ;bsupesup=1 with respect to the ;bsupâ.,"∞;esup-norm. The cospectrality cs(Km,;bsubesub) of the complete bipartite graph Km,;bsubesub for all positive integers m and n with m≤n<m-1+2m-1 is computed. As a consequence of the latter result, it is proved that in general there is no constant upper bound on |e-e′|, where e and e′ denote the number of edges of the graphs G and G′, respectively, such that cs(G)=λ(G,G′). In contrast we show that for such graphs G and G′, we have |e-e′|LE;1. In particular, |e-;bsupe′;esup|≤3e. © 2014 Elsevier Inc.