Two graphs are said to be \(Q\)-cospectral (respectively, \(A\)-cospectral) if they have the same signless Laplacian (respectively, adjacency) spectrum. A graph is said to be \(DQS\) (respectively, \(DAS\)) if there is no other non-isomorphic graphs \(Q\)-cospectral (respectively, \(A\)-cospectral) with it. A tree on \(n\) vertices with maximum degree \(d_1\) is called starlike and denoted by \(ST(n, d_1)\), if it has exactly one vertex with the degree greater than 2. A tree is called double starlike if it has exactly two vertices of degree greater than 2. If we attach \(p\) pendant vertices (vertices of degree 1) to each of pendant vertices of a path \(P_n\), the the resulting graph is called the double starlike tree \(H_n(p,p)\). In this article, we prove that all double starlike trees \(H_n(p,p)\) are \(DQS\), where \(p\geq 1, n\geq 2\) and \(p\) denotes . In addition, by a simple method, we show that all starlike trees are \(DQS\) excluding \(K_{1,3}=ST(4,3)\).
All graphs considered in this paper are simple and undirected. Let \(G = (V,E)\) be a graph with vertex set \(V(G) = \left\{ {v_1, \dots, v_n} \right\}\) and edge set \(E(G)\), where \(v_1, v_2,\ldots , v_n\) are indexed in the non-increasing order of degrees. Let \(d_i = d_i(G) = d_{G}(v_i)\) be the degree of the vertex \(v_i\), and \(deg(G) = (d_1=\Delta, d_2,\ldots , d_n)\) the non-increasing degree sequence of \(G\). We denote the line graph of \(G\) and the total number of triangles of \(G\) by \(G^{L}\) and \(t(G)\), respectively.
The adjacency matrix of \(G\), denoted by \(A(G)\), is the \(n\times n\) matrix whose \((i, j)\)-entry is \(1\) if \(v_i\) and \(v_j\) are adjacent and 0 otherwise. We call \(L(G) = D(G)-A(G)\) and \(Q(G) = D(G)+A(G)\) the Laplacian matrix of \(G\) and the signless Laplacian spectrum, respectively, where \(D(G)\) is the \(n\times n\) diagonal matrix with \(d_1, d_2,\ldots , d_n\) as diagonal entries. The eigenvalues of \(A(G)\), \(L(G)\) and \(Q(G)\) are called the adjacency eigenvalues, Laplacian eigenvalues and signless Laplacian eigenvalues of \(G\), respectively.
Denote by \(\lambda_1(G)\geq …\geq \lambda_n(G)\), \(\mu_1(G)\geq …\geq \mu_n(G)\) and \(q_1(G)\geq …\geq q_n(G)\) the adjacency eigenvalues, the Laplacian eigenvalues and signless Laplacian eigenvalues of \(G\), respectively. The multi-set of eigenvalues of \(Q(G)\) (respectively, \(L(G)\) and \(A(G)\)) is called the signless Laplacian (respectively, Laplacian and adjacency) spectrum of \(G\). We shall denote the signless Laplacian spectrum of \(G\) by \[{\rm{Spec}}_{Q}(G) = \Large\left\{ { [q_1(G)]^{ m_1 } , [q_2(G)]^{ m_2 } , \dots, [q _k(G)]^{ m_k} } \Large\right\},\] where \(m_i\) denotes the multiplicity of \(q_i(G)\), and \(q_{i}(G)\neq q_{j}(G)\) for all \(i\neq j\). Two graphs are said to be \(Q\)-cospectral (respectively, \(L\)-cospectral and \(A\)-cospectral) if they have the same signless Laplacian (respectively, Laplacian and adjacency) spectrum. A graph is said to be \(DQS\) (respectively, \(DLS\) and \(DAS\)) if there is no other non-isomorphic graphs \(Q\)-cospectral (respectively, \(L\)-cospectral and \(A\)-cospectral) with it.
In this paper, let \(P_n\), \(C_n\) and \(K_{1, n-1}\) denote the path, the cycle and the star of order \(n\), respectively. A tree is called starlike if it has exactly one vertex of degree greater than 2. We denote by \(ST(n, d_1)=T(l_1, l_2,\ldots , l_{\Delta})\) the starlike tree with maximum degree \(\Delta\) such that \[\label{eqn:ST-path} T(l_1, l_2,\ldots , l_{\Delta})-v=P_{l_1}\cup P_{l_2}\cup \dots \cup P_{l_\Delta}, \tag{1}\] where \(v\) is the vertex of degree \(\Delta\) in the starlike tree, \(l_1, l_2, \dots, l_\Delta\) are any positive integers. A starlike tree with maximum degree 3 is called a \(T\)-shape tree.
We call a tree double starlike if it has exactly two vertices of degree greater than two. Denote by \(H_n(p,q)\) the double starlike tree obtained by attaching \(p\) pendant vertices (vertices of degree 1) to one pendant vertex of \(P_n\) and \(q\) pendant vertices to the other pendant vertex of \(P_n\) (shown in Figure 1). In this paper, we prove that any starlike tree \(ST(n, d_1)\) and double starlike tree \(H_n(p, p)\) is determined by its signless Laplacian spectrum.
The problem “which graphs are determined by their spectra?” originates from chemistry. Günthard and Primas [8] raised this question in the context of Hückel’s theory. Since this problem is generally very difficult, van Dam and Haemers [17] proposed a more modest problem, that is “Which trees are determined by their spectra?” Here we introduce some results about spectral properties of the (double) starlike trees:
Lepović and Gutman proved that no two non-isomorphic starlike trees have the same adjacency spectrum (see [9]). Wang and Xu gave all \(T\)-shape trees which are determined by their adjacency spectra (see [19]), and proved that \(T\)-shape trees are \(DLS\) (see [18]). Omidi and Tajbakhsh proved that starlike trees are \(DLS\) (see [15]). Ghareghani et al. gave a method to construct a graph which has the same adjacency spectrum with a starlike tree (see [7]). Omidi gave all \(T\)-shape trees which are \(DQS\) (see [14]). Liu and et.al., proved that double starlike trees \(H_n(p, p)\) (\(n \geq 2, p \geq 1\)) are \(DLS\) (see [12]). Omidi and Vatandoost proved that starlike trees with maximum degree 4 are \(DQS\) (see [16]). Bu and Zhou proved that starlike trees whose maximum degree exceed 4 are \(DQS\) (see [2]). Lu and Liu proved that double starlike trees \(H_n(p,q)\) are \(DLS\) (see [13]).
In this article, we prove that all double starlike trees \(H_n(p,p)\) are \(DQS\). In addition, by a simple method, we show that all starlike trees are \(DQS\) excluding \(K_{1,3}=ST(4,3)\).
In this section, we give some lemmas playing an important role throughout this article.
Lemma 2.1 ([6]).Let G be a graph. For the adjacency matrix and Laplacian matrix, the following can be obtained from the spectrum:
(i) the total number of vertices,
(ii) the total number of edges.
For the adjacency matrix, the following follows from the spectrum:
(iii) the total number of closed walks of any length.
(iv) Being regular or not and the degree of regularity.
(v) Being bipartite or not.
For the Laplacian matrix, the following follows from the spectrum:
(vi) the total number of components.
Lemma 2.2([1]).Let \(G\) be a graph with \(n\) vertices, \(m\) edges and \(t\) triangles and vertex degrees \(d_1, d_2,\ldots , d_n\). Let \({T_k} = \sum\limits_{i = 1}^n {{{({q_i}(G))}^k}}\). Then
\(T_0=n\), \(T_1=\sum\limits_{i = 1}^n d_i=2m\), \(T_2=2m+\sum\limits_{i = 1}^n d^2_i\) and \(T_3=6t+3\sum\limits_{i = 1}^n d^2_i+\sum\limits_{i = 1}^n d^3_i\).
Lemma 2.3 ([4]).Let \(G\) be a simple graph. Then the total number of closed walks of length 4 is equal to twice the total number of edges plus four times of the total number of induced paths of length 2 plus eight times of the total number of 4-cycles.
Lemma 2.4([10]). Let \(G\) be a graph with \(V(G)\neq \phi\) and \(E(G)\neq \phi\). Then \[d_1+1 \leq \mu_1 \leq max \left\{ {\dfrac{{{d_i}({d_i} + {m_i}) + {d_j}({d_j} + {m_j})}}{{{d_i} + {d_j}}}|\,{v_i}{v_j} \in E(G)} \right\},\] where \(\mu_1\) is the largest eigenvalue of \(L(G)\), and \(m_i\) denotes the average of the degrees of the vertices adjacent to the vertex \(v_i\) in \(G\).
Lemma 2.5 ([17, 5])\({\rm{Spec}}_{Q}(P_n)\) is consists of \(0\) and \(2+2\cos\dfrac{\pi j}{n}\), for \(j=1, 2, \dots, n-1\). For a graph \(G\), \(0<q_1(G)< 4\) if and only if all components of \(G\) are paths.
Lemma 2.6([6, 5]) For any bipartite graph \(G\), \({\rm{Spec}}_{Q}(G)\) coincides with the \(L\)-spectrum of \(G\).
Lemma 2.7 ([6, 5]) For a connected graph \(G\), \(q_n(G)=0\) if and only if the graph is bipartite. In this case 0 is a simple eigenvalue, i.e., \(m_n=1\). The multiplicity of 0 as the signless Laplacian eigenvalue is equal to the total number of bipartite components.
Lemma 2.8 ([20) If two graphs \(G\) and \(H\) are \(Q\)-cospectral, then their line graphs are \(A\)-cospectral. The converse is true if \(G\) and \(H\) have the same number of vertices and edges.
Lemma 2.9 ([17) (Interlacing theorem) Suppose that \(N\) is a symmetric \(n\times n\) matrix with eigenvalues \(a_1\geq a_2\geq …\geq a_n\). Then the eigenvalues \(b_1\geq b_2\geq …\geq b_m\) of a principal submatrix of \(N\) of size \(m\) satisfy \(a_i\geq b_i\geq a_{n-m+i}\), for \(i=1, 2, \dots, m\).
Lemma 2.10 ([11) If \(G\) is a graph of order \(n\), then \(q_3(G)\geq d_3(G)-\sqrt{2}\).
Lemma 2.11 ([11) If \(G\) is a graph of order \(n\), then \(q_2(G)\geq d_2(G)-1\).
A connected graph with \(n\) vertices is said to be unicyclic if it has \(n\) edges. If the girth of a unicyclic graph is odd, then this unicyclic graph is said to be odd unicyclic.
Lemma 2.12 ([3) Let \(G\) be a graph \(Q\)-cospectral with a tree \(T\) of order \(n\). Then one of the following holds:
(1) \(G\) is tree;
(2) \(G\) is the union of a tree with \(f\) vertices and \(s\) odd unicyclic graphs, and \(n=4^sf\).
It is easy to see that \(K_{1,3}\) and \(K_3\sqcup K_1\) are \(Q\)-cospectral, i.e., \({\rm Spec}_{Q}(K_{1,3})={\rm Spec}_{Q}(K_{3}\sqcup K_1)=\{[4]^{1},[1]^{2},[0]^{1}\}\) (see Figure 1).
Remark 2.13 Note that:
(1) \(H_1(p, p)\cong K_{1, 2p}\). Any star graph is \(DQS\) excluding \(K_{1, 3}\)[11].
(2) \(H_n(1, 1)\cong P_{n+2}\). Any disjoint union of the path graphs is \(DQS\) [17].
So, we always assume that \(n, p\geq 2\) and the maximum degree of \(H_n(p, p)\), \(d_1(H_n(p, p))\), is greater than or equal to 3.
In this subsection, by a simple method, we show that any starlike tree \(ST(n, d_1)\) is \(DQS\) excluding \(ST(4, 3)\). To do so, first we need the following observation.
Lemma 3.1 \(q_2(ST(n, d_1))<4.\)
Proof. Let \(v_1\) be the unique vertex of \(ST(n, d_1)\) of degree \(d_1\). Let \(Y_{1}\) be the \((n-1)\times (n-1)\) principal submatrix of the signless Laplacian matrix of \(ST(n, d_1)\) obtained by removing the row and the column corresponding to \(v_1\). Then by (1) and Lemma 2.5, the largest signless Laplacian eigenvalues of \(Y_{1}\) is less than 4 (In fact, the several blocks of \(Y_{r}\) are principal submatrices of \(L(P_{l_{1+1}}),\dots ,L(P_{l_{d_{1}+1}})\) which are nonnegative and irreducible). So, by Lemma 2.9, \[4>q_1(Y_r)\ge q_2(ST(n, d_1)).\] ◻
Proposition 3.2 Let \(G\) be a connected graph such that \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(ST(n, d_1))\). Then \(G\cong ST(n, d_1)\).
Proof. It is clear by Lemmas 2.1 and 2.7 \(G\) has a bipartite component, \(n\) vertices and \(n-1\) edges. So, \(G\) is a tree. We know that \(ST(n, d_1)\) has one vertex of degree \(d_1> 2\), \(d_1\) vertices of degree 1 and \(n-d_1-1\) vertices of degree 2. Set \(F=max \left\{ {{d_1} + \frac{7}{{{d_1} + 2}},\,{d_1} + \frac{8}{{{d_1} + 2}},\,{d_1} + 1} \right\}\). It follows from Lemmas 2.4 and 2.6 that \(\mu_1(G)=q_1(G)\leq F\) (see Figure 2. Therefore, \(d_1(G)+1\leq \mu_1(G)=q_1(G)\leq F\). Hence \(d_1(G)\leq F-1<d_1+1\). So, \(d_1(G)\leq d_1\).
Denote by \(N_{k}\) the total number of vertices of degree \(k\in \left\{ {1,\,2,\,3,\,\dots,d_1(G)\leq d_1} \right\}\) in \(G\). By Lemma 2.1, \[\sum\limits_{k = 1}^{{d_1(G)}} {{N_k} = n}, \hspace{10mm} \sum\limits_{k = 1}^{{d_1(G)}} {k{N_k} = 2(n – 1)}, \hspace{10mm} \sum\limits_{k = 1}^{{d_1(G)}} {{k^2}{N_k} = {{d_1}^2}} + d_1 + 4(n – d_1-2).\]
Therefore, \[ \sum\limits_{k = 1}^{{d_1(G)}} (k^2-3k+2){N_k} = d^2_1-3d_1-2.\tag{3}\]
By Lemma 2.8, \(ST(n, d_1)^{L}\) and \(G^{L}\) are \(A\)-cospectral. In addition, by (iii) of Lemma 2.1, they have the same number of triangles (six times the total number of closed walks of length 3). In other words, \[\sum\limits_{i = 1}^{{d_1(G)}} {\left( {\begin{array}{*{20}{c}} k \\ 3 \end{array}} \right)} {N_k} = \left( {\begin{array}{*{20}{c}} {d_1} \\ 3 \end{array}} \right).\]
We aim to show that \(N_{d_1}=1\). Suppose that \(N_{d_1}=0\). To put that another way \(d_1(G)< d_1\). Then:
\[\left( {\begin{array}{*{20}{c}} {d_1} \\ 3 \end{array}} \right)=\sum\limits_{k = 1}^{{d_1(G)}} {\left( {\begin{array}{*{20}{c}} k \\ 3 \end{array}} \right)} {N_k}< \dfrac{d_1}{6} \sum\limits_{k = 1}^{{d_1(G)}}(k-1)(k-2)N_k.\]
Thus \[(d^2_1-3d_1-2)< \sum\limits_{k = 1}^{{d_1(G)}} (k^2-3k+2){N_k},\] a contradiction to (3). Therefore, \(N_{d_1}\geq 1\). Up to now, we have shown that \(G\) has at least one vertex with maximum degree \(d_1\), say \(v_1\). It follows from Lemma 3.1 that \(q_2(G)<4\). So by Lemma 2.11, \(d_2(G)<5\). Therefore, \(d_2(G)\in \left\{ {1,\,2,\,3,\,4} \right\}\). Assume that there are \(a\) vertices of degree \(1\), \(b\) vertices of degree \(2\), \(c\) vertices of degree \(3\), \(d\) vertices of degree \(4\) between \(v_2 \leqslant v_i \leqslant v_n\). \[\begin{cases} &a + b + c+d= n-1,\\ &a +2b + 3c+4d= 2(n-1)-d_1,\\ &a + 4b + 9c+16d=d^2_1+d_1-d^2_1+4(n-d_1-1)=d_1+4(n-d_1-1),\\ &a + 8b + 27c+64d =d^3_1+d_1-d^3_1+8(n-d_1-1)=d_1+8(n-d_1-1).\\ \end{cases}\]
The roots are \(a=d_1\), \(b=n-d_1-1\) and \(c=d=0\). Therefore, \(G\) is a tree with exactly one vertex of degree more than two. So, \(G\cong ST(n, d_1)\). This completes the proof. ◻
Proposition 3.3 Let \(G\) be a disconnected graph such that \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(ST(n, d_1))\). Then \(G\) has no triangles.
Proof. By Lemma 2.7, \(G\) has only one bipartite component. Consider the following two cases:
Case 1. \(\delta=d_n< 1\); i.e, \(\delta=d_n=0\). In this case, the bipartite component of \(G\) is only \(K_1\), since \(G\) has only one bipartite component (see Lemma 2.7) and the other components of \(G\) are odd unicyclic graphs. Therefore, \(G=K_1\cup H_1\cup …\cup H_c\), \((1\leq i\leq c)\), where \(H_i\)’s are odd unicyclic graphs. By notations of Lemma 2.12, \(f=1\). If \(c=1\), it follows from Lemma 2.12 that \(n=4\) and so \(G=K_1\cup H_1\). By Lemma 2.12, \(|V(ST(n, d_1))|=4\). Obviously, \(ST(n, d_1)=K_{1, 3}\) or \(ST(n, d_1)=P_4\) (there are two types trees of order 4). But, if \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(P_4)\), then \(G\) is \(DQS\) and \(G\cong P_4\). In this case \(G\) is connected, which is impossible. Hence we must have \({\rm{Spec}}_{Q}(G=K_1\cup H_1)={\rm{Spec}}_{Q}(K_{1,3})\) or \(G=K_1\cup K_3\). If \(t(G)\geq 2\), then we have two components which are odd unicyclic graphs and so \(q_2(G)\geq 4\), a contradiction with Lemma 3.1.
Case 2. \(\delta=d_n\geq 1\). By Lemma 2.12, if \(t(G)=1\), then \(G=Y\cup T\) (*), where \(Y\) and \(T\) are a connected graph consisting of a unique triangle and a tree on at least two vertices, respectively. This means that \(G\) must have at least \(a\) vertex with degree 3 or 4. Otherwise, \(G=kP_t\cup lC_r\) and by (*) we get \(G=C_3\cup P_{n-4}\). Clearly, \(q_1(G=C_3\cup P_{n-4})=4\). On the other hand, since \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(ST(n, d_1))\), thus \(ST(n, d_1)\) has \(K_{1, 3}\) as its proper induced subgraph and so \(q_1(G)=q_1(ST(n, d_1))>q_1(K_{1,3})=4\), a contradiction.
By using the previous notations, we get \[\begin{cases} &a + b + c+d= n-1,\\ &a +2b + 3c+4d= 2(n-1)-d_1,\\ &a + 4b + 9c+16d=d_1+4(n-1-d_1)-d^2_1,\\ &a + 8b + 27c+64d =d_1+8(n-1-d_1)-d^3_1-6.\\ &6c+24d=d_1(d_1-1)(d_1-2)-d_1(d_1-1)(d_1-2),\\ \end{cases}\]
Therefore, \(d=-1\), a contradiction. ◻
Proposition 3.4 Let \(G\) be a disconnected graph such that \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(ST(n, d_1))\). Then \(G \cong K_3\cup K_1\).
Proof. By Lemma 2.7, \(G\) has only one bipartite component. Consider the following two cases:
Case 1. \(\delta=d_n< 1\); i.e, \(\delta=d_n=0\). In this case, the bipartite component of \(G\) is only \(K_1\), since \(G\) has only one bipartite component (see Lemma 2.7) and the other components of \(G\) are odd unicyclic graphs. Therefore, \(G=K_1\cup H_1\cup …\cup H_c\), \((1\leq i\leq c)\) are odd unicyclic graphs. By notations of Lemma 2.12, \(f=1\). If \(c=1\), it follows from Lemma 2.12 that \(n=4\) and so \(G=K_1\cup H_1\). By Lemma 2.12, \(|V(ST(n, d_1))|=4\). Obviously, \(ST(n, d_1)=K_{1, 3}\) or \(ST(n, d_1)=P_4\) (there are two types trees of order 4). But, if \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(P_4)\), then \(G\) is \(DQS\) and \(G\cong P_4\). In this case \(G\) is connected, which is impossible. Hence we must have \({\rm{Spec}}_{Q}(G=K_1\cup H_1)={\rm{Spec}}_{Q}(K_{1,3})\) or \(G=K_1\cup K_3\). If \(c\geq 2\), we have two components which are odd unicyclic graphs and so \(q_2(G)\geq 4\), a contradiction with Lemma 3.1.
Case 2. \(\delta=d_n\geq 1\). By Lemma 2.12, if \(c=1\), then \(G=Y\cup T\), where \(Y\) and \(T\) are a connected graph consisting of a unique cycle of order at least \(5\) and a tree on at least two vertices, respectively. This means that \(G\) must have at least a vertex with degree 3 or 4. By using the previous notations, we get \[\begin{cases} &a + b + c+d= n-1,\\ &a +2b + 3c+4d= 2(n-1)-d_1,\\ &a + 4b + 9c+16d=d_1+4(n-d_1-1),\\ &a + 8b + 27c+64d =d_1+8(n-d_1-1).\\ \end{cases}\]
Therefore, \(c=d=0\), a contradiction. ◻
Combining Proposition 3.2 and Proposition 3.4 we have the following theorem.
Theorem 3.5 Let \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(ST(n, d_1))\). Then \(G\) is either \(ST(n, d_1)\) or \(K_3\cup K_1.\)
In [20], it was shown that for \(\Delta\geq 12\), the line graph of starlike trees are \(DAS\). Now, we present the following corollary.
Now, we present a corollary which immediately follows from Lemma 2.8 and Proposition 3.2.
Corollary 3.6 Let \(G\) be a connected graph such that \({\rm{Spec}}_{A}(G^{L})={\rm{Spec}}_{A}(ST(n, d_1)^{L})\) and \(|V(G)|=|V(ST(n, d_1))|\). Then \(G\cong ST(n, d_1)\) and so \(G^{L} \cong ST(n, d_1)^{L}\).
In this subsection, we show that any double starlike tree \(H_n(p,p)\) is \(DQS\). To do so, first we need the following observation.
Lemma 3.7 \(q_3(H_n(p, p) )<4\).
Proof. Let \(v_1\) and \(v_2\) be the vertices of \(H_n(p, p)\) with the degree \(p+1\). Let \(Y_{1,2}\) be the \((2p+n-2)\times (2p+n-2)\) principal submatrix of the signless Laplacian matrix of \(H_n(p, p)\) obtained by removing the rows and columns corresponding to \(v_1\) and \(v_2\). Then by (1) and Lemma 2.5, the largest signless Laplacian eigenvalue of \(Y_{1,2}\) is less than 4. By Lemma 2.9, \(q_3(H_n(p, p) )\leq q_1(Y_{1,2})< 4\). ◻
Proposition 3.8 Let \(G\) be connected graph such that \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p, p))\). Then \(G\) is a tree with exactly two vertices of degree \(p+1\).
Proof. It is clear by Lemma 2.7 that \(G\) has a bipartite component, \(n+2p\) vertices and \(n+2p-1\) edges. So, \(G\) is a tree, since \(G\) is connected. By Lemmas 2.4 and 2.6, we have \(d_1+1\leq q_1(G)=\mu_1(G)\leq p+2+\dfrac{1}{p+2}\) and so \(\Delta=d_1(G)\leq p+1\). Now, we show that \(d_1=d_2=p+1\). Denote by \(N_{k}\) the total number of vertices of degree \(k\in \left\{ {1,\,2,\,3,\,\dots,\,d_1\leq p+1} \right\}\) in \(G\). By Lemma 2.1,
\[\sum\limits_{k = 1}^{{d_1}} {{N_k} = n + 2p}, \quad\sum\limits_{k = 1}^{{d_1}} {k{N_k} = 2(n + 2p – 1)}, \quad\sum\limits_{k = 1}^{{d_1}} {{k^2}{N_k} = 2{{(p + 1)}^2}} + 2p + 4(n – 2).\]
Therefore, By adding up the first, second and third Equations with coefficients \(2\), \(-3\), \(1\), respectively we get:
\[\label{eqn:4.1} \sum\limits_{k = 1}^{{d_1}} {(k^2-3k+2){N_k} =2[(p+1)^2-3(p+1)+2]}.\tag{4}\] By Lemma 2.8, \(H_n(p, p)^{L}\) and \(G^{L}\) are \(A\)-cospectral. In addition, by Lemma 2.1 (iii), they have the same number of triangles (six times the total number of closed walks of length 3). In other words, \[\sum\limits_{i = 1}^{{d_1}} {\left( {\begin{array}{*{20}{c}} k \\ 3 \end{array}} \right)} {N_k} = 2 \left( {\begin{array}{*{20}{c}} {p + 1} \\ 3 \end{array}} \right).\]
We aim to show that \(N_{p+1}=2\). Consider the following cases:
Case 1. \(N_{p+1}=0\). To put that another way \(d_1< p+1\). Then:
\[2\left( {\begin{array}{*{20}{c}} {p + 1} \\ 3 \end{array}} \right)=\sum\limits_{k = 1}^{{d_1}} {\left( {\begin{array}{*{20}{c}} k \\ 3 \end{array}} \right)} {N_k}< \dfrac{p+1}{6} \sum\limits_{k = 1}^{{d_1}}(k-1)(k-2)N_k .\]
Thus \[2[(p+1)^2-3(p+1)+2]< \sum\limits_{k = 1}^{{d_1}} (k^2-3k+2){N_k},\] a contradiction to (4).
Case 2. \(N_{p+1}=1\). To put that another way, there exists only one vertex with degree \(d_1= p+1\). So \[2\left( {\begin{array}{*{20}{c}} {p + 1} \\ 3 \end{array}} \right)=\sum\limits_{i = 1}^{{d_1}} {\left( {\begin{array}{*{20}{c}} k \\ 3 \end{array}} \right)} {N_k}.\] i.e.,
\[2\dfrac{p+1}{6}[(p+1)^2-3(p+1)+2]=\dfrac{p+1}{6}[(p+1)^2-3(p+1)+2]+\sum\limits_{i = 1}^{{p}} \dfrac{k}{6}(k-1)(k-2) {N_k} ,\] i.e., \[\dfrac{p+1}{6}[(p+1)^2-3(p+1)+2]=\sum\limits_{i = 1}^{{p}} \dfrac{k}{6}(k-1)(k-2) {N_k}< \dfrac{p+1}{6}\sum\limits_{i = 1}^{{p}} (k-1)(k-2) {N_k},\] or \[\label{eqn:4.1-4} [(p+1)^2-3(p+1)+2]< \sum\limits_{i = 1}^{{p}} (k-1)(k-2) {N_k}.\tag{5}\]
Consequently, by (5) we get
\[\begin{aligned} 2[(p+1)^2-3(p+1)+2]=&[(p+1)^2-3(p+1)+2]+[(p+1)^2-3(p+1)+2] \\ <& [(p+1)^2-3(p+1)+2]+\sum\limits_{i = 1}^{{p}} (k-1)(k-2) {N_k}\\ =&\sum\limits_{i = 1}^{{p+1}} (k-1)(k-2) {N_k}\\ =&\sum\limits_{i = 1}^{{d_1}} (k^2-3k+2){N_k}, \end{aligned}\] a contradiction to (4). So, one may deduce that \(N_{p+1}=2\). ◻
Lemma 3.9 Let \(G\) be a connected graph such that \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p, p))\). Then \(G\) is a double starlike tree with \(deg(G)=(p + 1,p + 1,\,\underbrace {2,\,\dots,\,2}_{n – 2\,\hbox{times}},\underbrace {1,\,\dots,\,1}_{2p\,\hbox{times}})\).
Proof. It is clear by Lemma 2.1, \(G\) has a bipartite component, \(n+2p\) vertices and \(n+2p-1\) edges. So, \(G\) is a tree, since it is connected. Now, by Lemma 3.7, \(q_3(G)< 4\). By Lemma 2.10, \(d_3-\sqrt{2}\leqslant q_3(G)< 4\) and so \(d_3< 4+\sqrt{2}\approx 5.42\). Therefore, \(0<d_3\in \left\{ {1,\,2,\,3,\,4,\,5} \right\}\). Obviously, \(d_{n+2p}(G)=1\), since any tree has at least two vertices of degree 1. We know that \(d_1=d_2=p+1\). On the other hand, it follows from Lemmas 2.8 and 2.1 that \(t(G^{L})=t(H_n(p, p)^{L})=2\left( {\begin{array}{*{20}{c}} {p + 1} \\ 3 \end{array}} \right)= \sum\limits_{k = 1}^{{d_1}} \left( {\begin{array}{*{20}{c}} {k} \\ 3 \end{array}} \right)N_k\). Assume that there are \(a\) vertices of degree \(1\), \(b\) vertices of degree \(2\), \(c\) vertices of degree \(3\), \(d\) vertices of degree \(4\) and \(e\) vertices of degree 5 between \(v_2 \leqslant v_i \leqslant v_{n+2p}\).
\[\begin{cases} &a + b + c+d+e= n+2p-2,\\ &a +2b + 3c +4d+5e=2(n+2p-1)-x,\\ &a + 4b + 9c+16d+25e =2(p+1)^2+2p+4(n-2)-y,\\ &a + 8b + 27c+64d+125e =2(p+1)^3+2p+8(n-2)-w,\\ &6c+24d+60e =2p(p-1)(p+1)-z,\\ \end{cases}\] where \[\begin{aligned} x&=d_1+d_2=2p+2,\\ y&=d^2_1+d^2_2=2(p+1)^2,\\ w&=d^3_1+d^3_2=2(p+1)^3,\\ z&=d_1(d^2_1-3d_1+2)+d_2(d^2_2-3d_2+2)=2p(p-1)(p+1). \end{aligned}\]
It is easy to see that \(e=d=c=0\). Therefore, by the first and the second equations, we get \(b=n+2p-x=n+2p-(2p+2)=n-2\) and \(a=x-2=2p+2-2=2p\). This means that the connected tree \(G\) has exactly two vertices of degree more than two. So, \(G\) is a double starlike tree with \(deg(G)=(p + 1,p + 1,\,\underbrace {2,\,\dots,\,2}_{n – 2\,\hbox{times}},\underbrace {1,\,\dots,\,1}_{2p\,\hbox{times}})\). ◻
Proposition 3.10 The degrees sequence of the line graph of \(H_n(p, p)\) is \[(p + 1,p + 1,\,\underbrace {p,\,\dots,\,p}_{2p\,\hbox{times}},\underbrace {2,\,\dots,\,2}_{(n-3)\,\hbox{times}}).\]
Proof. Note that if \(uv\) is an edge belonging to \(H_n(p, p)\), then the vertex degree of \(uv\) in the line graph of \(H_n(p, p)\) is \(deg(u)+deg(v)-2\). Now, since \(deg(H_n(p, p))=(p + 2,p + 2,\,\underbrace {2,\,\dots,\,2}_{n – 2\,\hbox{times}},\underbrace {1,\,\dots,\,1}_{2p\,\hbox{times}})\) the proof is straightforward. ◻
Proposition 3.11 Let \(G\) be a connected graph such that \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p, p))\).
Proof. Let \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p, p))\). By Lemma 3.9, \(G\) is a double starlike tree with \(deg(G)=(p + 2,p + 2,\,\underbrace {2,\,\dots,\,2}_{n – 2\,\hbox{times}},\underbrace {1,\,\dots,\,1}_{2p\,\hbox{times}})\). We aim to show that \(G\cong H_n(p, p)\). To do so, we consider the following two cases:
Case 1. Two vertices of degree greater than two are adjacent in \(G\). Assume that there exist \(p-a\) (respectively, \(p-b\)) pendant vertices adjacent to the vertices of degree \(p+1\) in \(G\), where \(a\) and \(b\) are non-negative integers satisfying that \(0 \leq a,b \leq p\). Let \(m^i_{G^{L}}\) be the total number of vertices with degree \(i\) in \(G^{L}\). Therefore, \(m^{1}_{G^{L}}=a+b\), \(m^{2p}_{G^{L}}=1\), \(m^{p+1}_{G^{L}}=b\), \(m^{p}_{G^{L}}=p-b\), \(m^{p}_{G^{L}}=p-a\), \(m^{p+1}_{G^{L}}=a\), \(m^{2}_{G^{L}}=n-2-a-b\) and \(m^{k}_{G^{L}}=0\) for \(k \notin \left\{ {1,2,p,\,p + 1,2p} \right\}\). By Lemma 2.8, \(H_n(p, p)^L\) and \(G^{L}\) are \(A\)-cospectral. \(H_n(p, p)^{L}\) and \(G^{L}\) have the same number of edges and the same number of closed walks of length 4. Moreover, they have the same number of 4-cycles. Lemma 2.1 implies that \(H_n(p, p)^{L}\) and \(G^{L}\) have the same number of induced paths of length 2, that is,
\[\begin{aligned} 2\left( {\begin{array}{*{20}{c}} {p + 1} \\ 2 \end{array}} \right) + 2p\left( {\begin{array}{*{20}{c}} p \\ 2 \end{array}} \right) + (n – 3)\left( {\begin{array}{*{20}{c}} 2 \\ 2 \end{array}} \right) =& \left( {\begin{array}{*{20}{c}} {2p} \\ 2 \end{array}} \right) + b\left( {\begin{array}{*{20}{c}} {p + 1} \\ 2 \end{array}} \right) + (p – b)\left( {\begin{array}{*{20}{c}} p \\ 2 \end{array}} \right)\\ & + a\left( {\begin{array}{*{20}{c}} {p + 1} \\ 2 \end{array}} \right) + (p – b)\left( {\begin{array}{*{20}{c}} p \\ 2 \end{array}} \right)\\ & + (n – 2 – a – b)\left( {\begin{array}{*{20}{c}} 2 \\ 2 \end{array}}\right). \end{aligned}\]
It follows that \((p-1)^2+(a+b)(p-1)=0\), a contradiction, since \(0 \leq a,b\leq p\) and \(p\geq 2\).
Case 2. Two vertices of degree greater than two are non-adjacent in \(G\). As before, assume that there exist \(p-a\) (respectively, \(p-b\)) pendant vertices adjacent to the vertices of degree \(p+1\) in \(G\), where \(a\) and \(b\) are non-negative integers such that \(0 \leq a,b \leq p\). We show that \(a=b=0\). Then, by counting the total number of vertices in \(G\), we get \(K+\sum\limits_{j = 1}^a {{K_j}^\prime} + \sum\limits_{l = 1}^b {{K_j}^{''}} +2p=n+2p\) (see Figure 3). Hence \(K+a+b=n\). On the other hand, \(m^{1}_{G^{L}}=a+b\), \(m^{p+1}_{G^{L}}=b+1\), \(m^{p}_{G^{L}}=p-b\), \(m^{p+1}_{G^{L}}=a+1\), \(m^{p}_{G^{L}}=p-a\), \(m^{2}_{G^{L}}=n-3-a-b\) and \(m^{k}_{G^{L}}=0\) for \(k \notin \left\{ {1,2,p,\,p + 1} \right\}\). Note that \(H_n(p, p)^{L}\) and \(G^{L}\) are \(A\)-cospectral. By Lemma 2.1, \(H_n(p, p)^{L}\) and \(G^{L}\) have the same number of edges and the same number of closed walks of length 4. Moreover, they have the same number of 4-cycles. Lemma 2.8 implies that \(H_n(p, p)^{L}\) and \(G^{L}\) have the same number of induced paths of length 2, that is, \[\begin{aligned} 2\left( {\begin{array}{*{20}{c}} {p + 1} \\ 2 \end{array}} \right) + 2p\left( {\begin{array}{*{20}{c}} p \\ 2 \end{array}} \right) + (n – 3)\left( {\begin{array}{*{20}{c}} 2 \\ 2 \end{array}} \right) =& (b+1)\left( {\begin{array}{*{20}{c}} {p+1} \\ 2 \end{array}} \right) + (p-b)\left( {\begin{array}{*{20}{c}} {p } \\ 2 \end{array}} \right)\\ & + (a+1)\left( {\begin{array}{*{20}{c}} {p + 1} \\ 2 \end{array}} \right)+ (p – a)\left( {\begin{array}{*{20}{c}} p \\ 2 \end{array}} \right)\\ & + (n – 3 – a – b)\left( {\begin{array}{*{20}{c}} 2 \\ 2 \end{array}} \right). \end{aligned}\]
By a simple computation, we get \((a+b)(p-1)=0\) and so \(a=b=0\). Therefore, \(K=n\). This means that \(G\cong H_n(p, p)\) and the proof is completed. ◻
Proposition 3.12 Let \(G\) be a disconnected graph such that \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p,p))\). Then \(G\) has no triangles.
Proof. By Lemma 2.7, \(G\) has one bipartite component. We aim to
show that \(t(G)=0\). Suppose by the
contrary that \(t(G)\geq 1\). Obviously
\(t(G)\leq 2\), otherwise since \(G\) is disconnected, by Lemma 2.12, \(G\) has at least three odd unicyclic
components that any of them has a triangle. So \(q_1(G), q_2(G),q_3(G) \geq 4\), a
contradiction with Lemma 3.7. Suppose that \(t(G)=1\). Consider the following two
cases:
Case 1. \(\delta=d_n<
1\); i.e, \(\delta=d_n=0\).
Since, \(G\) has only one bipartite
component, so one may deduce that \(G\)
has only one isolated vertex.
Subcase 1.1. By Lemma 2.12, \(G=K_1\cup H_1\), where \(H_1\) is an odd unicyclic graph consisting of a triangle. By Lemma 2.8,
\(t(G^{L})=t(H_n(p, p)^{L})=2 \left( {\begin{array}{*{20}{c}} {p + 1} \\ 3 \end{array}} \right)\).
Assume that there are \(a\) vertices of degree \(1\), \(b\) vertices of degree \(2\), \(c\) vertices of degree \(3\), \(d\) vertices of degree \(4\) and \(e\) vertices of degree 5 between \(v_3 \leqslant v_i \leqslant v_{n+2p-1}\). \[\begin{cases} &a + b + c+d+e= n+2p-3,\\ &a +2b + 3c +4d+5e=2(n+2p-1)-x,\\ &a + 4b + 9c+16d+25e =2(p+1)^2+2p+4(n-2)-y,\\ &a + 8b + 27c+64d+125e =2(p+1)^3+2p+8(n-2)-6-w,\\ &6c+24d+60e =2p(p-1)(p+1)-z,\\ \end{cases}\] where \(x=d_1+d_2\), \(y=d^2_1+d^2_2\), \(w=d^3_1+d^3_2\) and \(z=d_1(d^2_1- 3d_1+2)+d_2(d^2_2- 3d_2+2)\). By a simple computation, \(d=\dfrac{-48(2x-3y+w-z+6)}{12}<0\), a contradiction, since \(2x-3y+w-z=0\).
Subcase 1.2. Let \(t(G)=2\), by a similar argument, and by using the previous notations, we get \(G=K_1\cup H_1\cup H_2\) and so \[\begin{cases} &a + b + c+d+e= n+2p-3,\\ &a +2b + 3c +4d+5e=2(n+2p-1)-x,\\ &a + 4b + 9c+16d+25e =2(p+1)^2+2p+4(n-2)-y,\\ &a + 8b + 27c+64d+125e =2(p+1)^3+2p+8(n-2)-12-w,\\ &6c+24d+60e =2p(p-1)(p+1)-z.\\ \end{cases}\]
By a simple computation, \(d=\dfrac{-48(2x-3y+w-z+12)}{12}<0\), which is a contradiction (since \(2x-3y+w-z=0\)).
Case 2. \(\delta=d_n\geq 1\). By Lemma 2.12, if \(t(G)=1\), then \(G=Y\cup T\), where \(Y\) and \(T\) are a connected graph consisting of a triangle and a tree on at least two vertices, respectively. Consider the following two cases:
Subcase 2.1. By using the previous notations, we get
\[\begin{cases} &a + b + c+d+e= n+2p-2,\\ &a +2b + 3c +4d+5e=2(n+2p-1)-x,\\ &a + 4b + 9c+16d+25e =2(p+1)^2+2p+4(n-2)-y,\\ &a + 8b + 27c+64d+125e =2(p+1)^3+2p+8(n-2)-6-w,\\ &6c+24d+60e =2p(p-1)(p+1)-z.\\ \end{cases}\]
Therefore, \(d=\dfrac{-48(2x-3y+w-z+6)}{12}<0\), which is a contradiction (since \(2x-3y+w-z=0\)).
Subcase 2.2. Suppose that \(t=2\), so by Lemma 2.12, \(G=T \cup Y_1\cup Y_2\), where \(Y_i\) denotes a connected graph consisting of a triangle and \(T\) is a tree on at least two vertices. By using the previous notations,
\[\begin{cases} &a + b + c+d+e= n+2p-2,\\ &a +2b + 3c +4d+5e=2(n+2p-1)-x,\\ &a + 4b + 9c+16d+25e =2(p+1)^2+2p+4(n-2)-y,\\ &a + 8b + 27c+64d+125e =2(p+1)^3+2p+8(n-2)-12-w,\\ &6c+24d+60e =2p(p-1)(p+1)-z.\\ \end{cases}\]
Therefore, \(d=\dfrac{-48(2x-3y+w-z+12)}{12}<0\), which is a contradiction (since \(2x-3y+w-z=0\)). ◻
Proposition 3.13 There is no disconnected graph \(Q\)-cospectral with \(H_n(p,p), (n, p\geq 2)\).
Proof. Let \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p,p))\) and \(G\) be disconnected. By Proposition 3.12, \(G\) has no triangles, i.e., \(t(G)=0\). Similar to Proposition 3.12 we have the following two case:
Case 1. \(d_1(G)=0\). By Lemma 2.12, if \(s=1\), then \(G=Y\cup T\), where \(Y\) is a connected graph consisting of a unique cycle of order at least \(5\) and \(T=K_1\). On the other hand, Lemma 2.12 implies that \(H_n(p,p)\) is either \(K_{1,3}\) or \(P_4\), a contradiction. So, let \(s=2\). In this case \(G=Y_1\cup Y_2\cup K_1\), where \(Y_i\) is a connected graph consisting of a unique cycle of order at least \(5\). It is clear that \(|V(G)|=16\) and \(|E(G)|=15\). Since \({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p,p))\), \(|V(G)|=|V(H_n(p,p))=n+2p\). Therefore, \(n+2p=16\) and \((n, p)\in \left\{ {(2, 7), (4, 6), (6, 5), (8, 4), (10, 3), (12, 2) } \right\}\). Applying the previous notations for \((n, p)=(2,7)\) we get \[\begin{cases} &a + b + c+d+e =13,\\ &a +2b + 3c +4d+5e= 2(2+14-1)-x,\\ &a + 4b + 9c+16d+25e =2(2+1)^2+4(2-2)+14-y,\\ &a + 8b + 27c+64d+125e =2(2+1)^3+14+8(2-2)-w,\\ &6c+24d+60e =2(8)(7)(6)-z.\\ \end{cases}\]
(Note that the degree of one of vertices is \(\delta=0\) and the two others degrees are \(d_1, d_2\). We can subtract these three vertices from 16. So, the total number of vertices with degrees 1, 2, 3, 4 and 5 is 13.). Then \(e=\dfrac{12(2x-3y+w-z+640)}{12}\) and so \(e=640\), a contradiction. By solving the system of equations for \((10, 3)\), \(e=\dfrac{12(2x-3y+w-z+1948)}{12}\) and so \(e=1948\), a contradiction. In a similar way, one can show that by replacing any of the above cases in the system of equations, we will have a contradiction. If \(s\geq 3\), then \(q_1(G), q_2(G), q_3(G)\geq 4\), a contradiction with Lemma 3.7.
Case 2. \(d_1(G)\geq 1\). Applying the previous notations we get \[\begin{cases} &a + b + c+d+e= n+2p-2,\\ &a +2b + 3c +4d+5e=2(n+2p-1)-x,\\ &a + 4b + 9c+16d+25e =2(p+1)^2+2p+4(n-2)-y,\\ &a + 8b + 27c+64d+125e =2(p+1)^3+2p+8(n-2)-12-w,\\ &6c+24d+60e =2p(p-1)(p+1)-z.\\ \end{cases}\]
Since \(G\) is disconnected, by Lemma 2.12, \(G\) consists of at least an odd unicyclic component such that the order of its odd cycle is greater than or equal to 5. This means that \(G\) has at least one vertex of degree either 3 or 4 or 5. But, by solving the system of equations, we get \(c=e=d=0\), which is impossible. ◻
Combining Proposition 3.11 and Proposition 3.13 we have the following results.
Corollary 3.14 Any double starlike tree \(H_n(p,p), (n, p\geq 2)\) is \(DQS\).
Theorem 3.15 Let \({\rm{Spec}}_{A}(G^{L})={\rm{Spec}}_{A}(H_n(p, p)^{L})\) and \(|V(G)|=|V(H_n(p, p))|\). Then \(G^{L}\cong H_n(p, p)^{L}\).
Proof. By Lemma 2.8, \({\rm{Spec}}_{A}(G^{L})={\rm{Spec}}_{A}(H_n(p,
p)^{L})\) implies that
\({\rm{Spec}}_{Q}(G)={\rm{Spec}}_{Q}(H_n(p,
p))\) and by Lemma 2.10, \(G\cong H_n(p, p)\). Therefore, \(G^{L}\cong H_n(p, p)^{L}\). ◻