Cospectrality of graphs

摘要

Richard Brualdi proposed ill St.evanivi? (2007) [6] the following problem: (Problem AWGS.4) Let G_n and G'_n be two lionisomorphic graphs on n vertices with spectra λ_1≥λ_2≥···≥λ_n and λ'_1≥λ'_2≥···≥λ'_n, respectively. Define the distance between the spectra of G_n and G'_n as λ(G_n,G'_n) = sun from i=1 to n(λ_i-λ'_i)~2 (or use sum from i=1 to n|λ_i-λ'_i|). Define the cospectrality of G_n by cs(G_n) = min{ λ(G_n, G'_n): G'_n not isomorphic to G_n}. Let cs_n = max{cs(G_n): G_n a graph on n vertices}. Problem A. Investigate cs(G_n) for special classes of graphs. Problem B. Find a good upper bound on cs_n. In this paper we study Problem A and determine the cospectrality of certain graphs by the Euclidian distance. Let K_n denote the complete graph on n vertices, nK_1 denote the null graph on n vertices and K_2 + (n - 2)K_1 denote the disjoint union of the K_2 with n - 2 isolated vertices, where n ≥ 2. In this paper we find cs(K_n), cs(nK_1), cs(K_2 + (n - 2)K_1) (n ≥ 2) and cs(K_(n,n)).