Cospectrality of multipartite graphs

Abstract

Let G be a graph on n vertices and consider the adjacency spectrum of G as the ordered n-tuple whose entries are eigenvalues of G written decreasingly. Let G and H be two non-isomorphic graphs on n vertices with spectra S and T, respectively. Define the distance between the spectra of G and H as the distance of S and T to a norm N of the n-dimensional vector space over real numbers. Define the cospectrality of G as the minimum of distances between the spectrum of G and spectra of all other non-isomorphic n vertices graphs to the norm N. In this paper we investigate copsectralities of the cocktail party graph and the complete tripartite graph with parts of the same size to the Euclidean or Manhattan norms. © 2022 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.