Which $L$-cospectral graphs have same degree sequences

Abstract

Let $\hat{I}{»}_i(G)$ be the $i$-th largest Laplacian eigenvalues of graph $G$, where $1\le i\le |V(G)|$. Liu, Yuan, You and Chen [Discrete Math., 341 (2018) 2969--2976] raised the problem for ``Which cospectral graphs have same degree sequences". In this paper, let $W_3$ and $W_5$ be the two graphs as shown in Fig. 2 and let $G$ be a connected graph with $n\ge 18$ vertices. We shall show that: $(1)$ If $\hat{I}{»}_2(G)<5<n-1<\hat{I}{»}_1(G)$, $\hat{I}{»}_1(G)\notin \{\hat{I}{»}_1(W_3),\hat{I}{»}_1(W_5)\}$ and $H$ is Laplacian cospectral with $G$, then $H$ must have the same degree sequence with $G$; $(2)$ If $\hat{I}{»}_2(G)\le 4.7<n-2<\hat{I}{»}_1(G)$, and $H$ is Laplacian cospectral with $G$, then $H$ must have the same degree sequence with $G$. The former result easily leads to the unique theorem result of [Discrete Math., 308 (2008) 4267--4271], that is: Every multi-fan graph $K_1\vee (P_{l_1}\cup P_{l_1}\cup \cdots \cup P_{l_t})$ is determined by the Laplacian spectrum. Moreover, it can also deduce a new conclusion: $K_1\vee (P_{l_1}\cup P_{l_1}\cup \cdots \cup P_{l_t}\cup C_{s_1}\cup C_{s_2}\cup \cdots \cup C_{s_k})$ $(t\ge 1,k\ge 1)$ is determined by the Laplacian spectrum if the graph order $n\ge 18$ and each $s_i$ $(i=1,2,\dots ,k)$ is odd.