Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6416428 | Linear Algebra and its Applications | 2014 | 13 Pages |
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).