Summary: Richard Brualdi proposed in [D. Stevanović, Linear Algebra Appl. 423, 172–181 (2007; Zbl 1290.05002)] the following problem (Problem AWGS.4): Let \(G_n\) and \(G_n'\) be two nonisomorphic graphs on \(n\) vertices with spectra \[ \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \,\text{and}\, \lambda_1' \geq \lambda_2' \geq \cdots \geq \lambda_n', \] respectively. Define the distance between the spectra of \(G_n\) and \(G_n'\) as \[ \lambda(G_n, G_n') = \sum_{i = 1}^n(\lambda_i - \lambda_i')^2(\text{or\,use\,} \sum_{i = 1}^n | \lambda_i - \lambda_i' |). \] Define the cospectrality of \(G_n\) by \[ \operatorname{cs}(G_n) = \min \{\lambda(G_n, G_n') : G_n' \text{ not isomorphic to } G_n \}. \] Let \[ \operatorname{cs}_n = \max \{\operatorname{cs}(G_n) : G_n \text{\,a\,graph\,on\,} n \text{\,vertices}\}. \] Problem A. Investigate \(\operatorname{cs}(G_n)\) for special classes of graphs.
Problem B. Find a good upper bound on \(\operatorname{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, \(n K_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 \geq 2\). In this paper we find \(\operatorname{cs}(K_n)\), \(\operatorname{cs}(n K_1)\), \(\operatorname{cs}(K_2 +(n - 2) K_1\)) \((n \geq 2)\) and \(\operatorname{cs}(K_{n, n})\).