Distance between spectra of graphs

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≥⋯≥λnandλ1′≥λ2′≥⋯≥λn′, respectively. Define the distance between the spectra of Gn and Gn′ asλ(Gn,Gn′)=∑i=1n(λi−λi′)2(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}. Problem AInvestigate cs(Gn) for special classes of graphs.Problem BFind 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 1≤p<∞ and csn=1 with respect to the ℓ∞-norm. The cospectrality cs(Km,n) of the complete bipartite graph Km,n for all positive integers m and n with m≤n