Wen Fei, Yan Juan, Huang Qiongxiang, Huang Xueyi: On the degree sequence determined by the Laplacian spectrum of the corresponding graph, 67-81

Abstract:

Let $\mathcal{G}(\Delta^{x_{\Delta}},\ldots, 2^{x_{2}},1^{x_{1}})$ be the set of connected graph with degree sequence $(\Delta^{x_{\Delta}},$ $\ldots,2^{x_{2}},1^{x_{1}})$. In this paper, we show that the degree sequences of $\mathcal{G}(3^{n_3},2^{n_2},1^{n_1})$ and $\mathcal{G}(4^{n_4},2^{n_2},1^{n_1})$ are determined by Laplacian spectrum with some restrictions. By those results we obtain that sun graph [4], $C_{n}\circ2K_{1}$[6] and $\mathcal{G}(4^1,2^{n-3},1^2)$ are determined by their Laplacian spectra. Furthermore, we prove that any graph $G\in\mathcal{G}(\Delta^{1},2^{n_2},1^{n_1})~(\Delta\ge 3)$, whose degree sequence is determined by Laplacian spectrum except that $G$ is a bicyclic graph with $\Delta=4$. Moreover, if $G$ is a bicyclic graph with $\Delta=4$, then $G$ may be $L$-cospectral to a graph with degree sequence $(3^{3},2^{n_{2}-3}, 1^{n_{1}+1})$. Applying this result we conclude that some graphs such as starlike trees[22], unicyclic graph $U_{n,p}$[27], friendship graph and butterfly graph et al. are determined by their Laplacian spectra. Moreover, we give a Laplacian spectral characterization of the degree sequence of $p$-rose graph which supports Liu's conjecture [19].with $n$

Key Words: Degree sequence, Laplacian spectrum, spectral characterization, cospectral graph.

2010 Mathematics Subject Classification: Primary 05C50.