Laplacian spectral characterization of setosa graphs

A setosa graph SG(e,f,g,h,d;b_۱,b_۲,\ldots,b_s) is a graph consisting of five cycles and s(\geq ۱) paths P_{b_۱+۱}, P_{b_۲+۱},\ldots,P_{b_s+۱} intersecting in a single vertex that all meet in one vertex, where b_i\geq۱ (for i=۱,\ldots,s) and e,f,g,h,d\geq ۳ denote the length of the cycles C_e, C_f, C_g, C_h and C_d, 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.

کلیدواژه ها:

DLS graphs ، Laplacian matrix ، Laplacian spectrum ، L-cospectral graphs ، Setosa graph