GRAPHS COSPECTRAL WITH MULTICONE GRAPHS Kw L(P )

Abstract

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