Cospectrality of graphs

Abstract

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≥⋯ ≥ λn and λ1′≥ λ2′≥⋯≥λn′, respectively. Define the distance between the spectra of Gn and Gn′ asλ(G n,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):G n a graph on n vertices}. Investigate cs(Gn) for special classes of graphs. Find 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(n K1), cs(K2+(n-2)K1) (n≥2) and cs(Kn, n).© 2014 PublishedbyElsevierInc.