GRAPHS COSPECTRAL WITH MULTICONE GRAPHS Kw 5 L(P)

ALI ZEYDI ABDIAN

[PDF]

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 innite 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 dened 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.

Keywords

adjacency spectrum, Laplacian spectrum, DS graph, line graph of Petersen graph.