Cospectrality of complete bipartite graphs

Richard Brualdi proposed in [Research problems from the Aveiro workshop on graph spectra, Linear Algebra Appl. 2007; 423: 172-181] the following problem: (Problem AWGS. 4) Let G(n) and G'(n) be two non-isomorphic graphs on n vertices with spectra. lambda(1) >= lambda(2) >= ... >= lambda(n) and lambda'(1) >= lambda'(2) >= lambda'(n,) respectively. Define the distance between the spectra of G(n) and G'(n) as.(G(n), G'(n)) = n i= 1 (.i -. i) 2.. or use n i= 1 |.i -. i |... Define the cospectrality of Gn by cs(G(n)) = min{.(Gn, G'(n)) : G'(n) not isomorphic to G(n)}. Let csn = max{cs(G(n)) : Gn a graph on n vertices}. Problem A Investigate cs(G(n)) for special classes of graphs. Problem B Find a good upper bound on csn. In this paper, we study ProblemAand determine the cospectrality of all complete bipartite graphs by the Euclidian distance. More precisely, we show that for all positive integers m and n there are some positive integers r, s and a non-negative integer t such that cs(Km, n) =.(Km, n, Kr, s+ tK1), where Km, n is the complete bipartite graph with parts of sizes m and n.