Cospectrality of graphs

Richard Brualdi proposed in Stevanivić (2007) [6] 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 study Problem A and determine the cospectrality of certain graphs by the Euclidian distance.Let Kn denote the complete graph on n vertices, nK1 denote the null graph on n vertices and K2+(n−2)K1 denote the disjoint union of the K2 with n−2 isolated vertices, where n⩾2. In this paper we find cs(Kn), cs(nK1), cs(K2+(n−2)K1) (n⩾2) and cs(Kn,n).