Laplacian spectral characterization of setosa graphs

A setosa graph SG(e, f, g, h, d; b1, b2, . . . , bs) is a graph consisting of five cycles and s(≥ 1) paths Pb1+1, Pb2+1, . . . , Pbs+1 intersecting in a single vertex that all meet in one vertex, where bi ≥ 1 (for i = 1, . . . , s) and e, f, g, h, d ≥ 3 denote the length of the cycles Ce, Cf , Cg, Ch and Cd, respectively. Two graphs G and H are L-cospectral if they have the same Laplacian spectrum. A graph G is said to be determined by the spectrum of its Laplacian matrix (DLS, for short) if every graph with the same Laplacian spectrum is isomorphic to G. In this paper we prove that if H is a L-cospectral graph with a setosa graph G, then H is also a setosa graph and the degree sequence of G and H are the same. We conjecture that all setosa graphs are DLS.