Graphs cospectral with multicone graphs KW 5 L(P)

Abstract

E. R. van Dam and W. H. Haemers [15] conjectured that almost all graphs are determined by their spectra. Nevertheless, the set of graphs which are known to be determined by their spectra is small. Hence, discovering infinite classes of graphs that are determined by their spectra can be an interesting problem. The aim of this paper is to characterize new classes of multicone graphs that are determined by their spectrum. A multicone graph is defined to be the join of a clique and a regular graph. It is proved that any graph cospectral with multicone graph Kw 5 L(P) is determined by its adjacency spectrum as well as its Laplacian spectrum, where Kw and L(P) denote a complete graph on w vertices and the line graph of the Petersen graph, respectively. Finally, three problems for further researches are proposed.