Graphs determined by signless Laplacian spectra

Abstract

In the past decades, graphs that are determined by their spectrum have received more attention, since they have been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. An important part of spectral graph theory is devoted to determining whether given graphs or classes of graphs are determined by their spectra or not. So, finding and introducing any class of graphs which are determined by their spectra can be an interesting and important problem. A graph is said to be $DQS$ if there is no other non-isomorphic graph with the same signless Laplacian spectrum. For a $DQS$ graph $G$, we show that $G\cup r{K}_1\cup s{K}_2$ is $DQS$ under certain conditions, where $r$, $s$ are natural numbers and $K_1$ and$K_2$ denote the complete graphs on one vertex and two vertices, respectively. Applying these results, some $DQS$ graphs with independent edges and isolated vertices are obtained.

Keywords:

• Spectral characterization
• Signless Laplacian spectrum
• Cospectral graph

1 Introduction

Let $G=(V,E)$ be a simple graph with vertex set $V=V\left(G\right)=\left\{v_1,\dots ,v_n\right\}$ and edge set $E=E\left(G\right)=\left\{e_1,\dots ,e_m\right\}$. Denote by $d\left(v\right)$ the degree of vertex $v$. All graphs considered here are simple and undirected. All notions on graphs that are not defined here can be found in [1–5]. The join of two graphs $G$ and $H$ is a graph formed from disjoint copies of $G$ and $H$ by connecting each vertex of $G$ to each vertex of $H$. We denote the join of two graphs $G$ and $H$ by $G▽H$. The complement of a graph $G$ is denoted by $\overline{G}$.

Let $A\left(G\right)$ be the $(0,1)$-adjacency matrix of graph $G$. The characteristic polynomial of $G$ is $det(\lambda I-A\left(G\right))$, and it is denoted by $P_G\left(\lambda \right)$. Let ${\lambda }_1$, ${\lambda }_2$, …, ${\lambda }_n$ be the distinct eigenvalues of $G$ with multiplicities $m_1$, $m_2$, …, $m_n$, respectively. The multi-set of eigenvalues of $Q\left(G\right)$ is called the signless Laplacian spectrum of $G$. The matrices $L\left(G\right)=D\left(G\right)-A\left(G\right)$ and $Q\left(G\right)=SL\left(G\right)=D\left(G\right)+A\left(G\right)$ are called the Laplacian matrix and the signless Laplacian matrix of $G$, respectively, where $D\left(G\right)$ denotes the degree matrix. Note that $D\left(G\right)$ is diagonal. The multi-set ${\mathrm{Spec}}_Q\left(G\right)=\left\{{\left[{\lambda }_1\right]}^{m_1},{\left[{\lambda }_2\right]}^{m_2},\dots ,{\left[{\lambda }_n\right]}^{m_n}\right\}$ of eigenvalues of $Q\left(G\right)$ is called the signless Laplacian spectrum of $G$, where $m_i$ denote the multiplicities of ${\lambda }_i$. The Laplacian spectrum is defined analogously.

For any bipartite graph, its $Q$-spectrum coincides with its $L$-spectrum. Two graphs are $Q$-cospectral (resp. $L$-cospectral, $A$-cospectral) if they have the same $Q$-spectrum (resp. $L$-spectrum, $A$-spectrum). A graph $G$ is said to be $DQS$ (resp. $DLS$, $DAS$) if there is no other non-isomorphic graph $Q$-cospectral (resp. $L$-cospectral, $A$-cospectral) with $G$. Van Dam and Haemers [6] conjectured that almost all graphs are determined by their spectra. Nevertheless, the set of graphs that are known to be determined by their spectra is too small. So, discovering infinite classes of graphs that are determined by their spectra can be an interesting problem. About the background of the question “Which graphs are determined by their spectrum?”, we refer to [6]. It is interesting to construct new $DQS$ ($DLS$) graphs from known $DQS$ ($DLS$) graphs. For a $DLS$ graph $G$, the join $G\cup r{K}_1$ is also $DLS$ under some conditions [7]. Actually, a graph is $DLS$ if and only if its complement is $DLS$. Hence we can obtain $DLS$ graphs from known $DLS$ graphs by adding independent edges.

Up to now, only some graphs with special structures are shown to be determined by their spectra (DS, for short) (see [1,8–30] and the references cited in them).

In this paper, we investigate signless Laplacian spectral characterization of graphs with independent edges and isolated vertices. For a $DQS$ graph $G$, we show that $G\cup r{K}_1\cup s{K}_2$ is $DQS$ under certain conditions. Applying these results, some $DQS$ graphs with independent edges and isolated vertices are obtained.

2 Some definitions and preliminaries

Some useful established results about the spectrum are presented in this section, will play an important role throughout this paper.

Lemma 2.1

[4,9,17] For the adjacency matrix, the Laplacian matrix and the signless Laplacian matrix of a graph $G$, the following can be deduced from the spectrum:

(1) The number of vertices.

(2) The number of edges.

(3) Whether G is regular.

For the Laplacian matrix, the following follows from the spectrum:

(4) The number of components.

For the signless Laplacian matrix, the following follow from the spectrum:

(5) The number of bipartite components.

(6) The sum of the squares of degrees of vertices.

Lemma 2.2

[17] Let $G$ be a graph with $n$ vertices, $m$ edges and $t$ triangles and vertex degrees $d_1,d_2,\dots ,d_n$. Let $T_k={\sum }_{i=1}^n{\left(q_i\left(G\right)\right)}^k$, then $$T_0=n,T_1=\sum _{i=1}^n{d}_i=2m,T_2=2m+\sum _{i=1}^n{d}_i^2\text{and}{T}_3=6t+3\sum _{i=1}^n{d}_i^2+\sum _{i=1}^n{d}_i^3.$$

For a graph $G$, let $P_L\left(G\right)$ and $P_Q\left(G\right)$ denote the product of all nonzero eigenvalues of $L_G$ and $Q_G$, respectively. We assume that $P_L\left(G\right)=P_Q\left(G\right)=1$ if $G$ has no edges.

Lemma 2.3

[4] For any connected bipartite graph $G$ of order $n$, we have $P_Q\left(G\right)=P_L\left(G\right)=n\tau \left(G\right)$, where $\tau \left(G\right)$ is the number of spanning trees of $G$.

For a connected graph $G$ with $n$ vertices and $m$ edges, $G$ is called unicyclic (resp. bicyclic) if $m=n$ (resp. $m=n+1$). If $G$ is a unicyclic graph that contains an odd (resp. even) cycle, then $G$ is called odd unicyclic (resp. even unicyclic).

Lemma 2.4

[31] For any graph $G$, $det\left(Q_G\right)=4$ if and only if $G$ is an odd unicyclic graph. If $G$ is a non-bipartite connected graph and $\left|E\left(G\right)\right|>\left|V\left(G\right)\right|$, then $det\left(Q_G\right)>16$, with equality if and only if $G$ is a non-bipartite bicyclic graph with $C_4$ as its induced subgraph.

Lemma 2.5

[32] Let $H$ be a proper subgraph of a connected graph $G$. Then, $q_1\left(G\right)>q_1\left(H\right)$.

3 Main results

We first investigate spectral characterizations of the union of a tree and several complete graphs $K_1$ and $K_2$.

Theorem 3.1

Let $T$ be a $DLS$( $DQS$) tree of order $n$. Then $T\cup r{K}_1\cup s{K}_2$ is $DLS$. $$T\cup r{K}_1\cup s{K}_2\text{is}DQS\text{if}n\text{is not divisible by}2\text{and}s=1.$$

Proof

Let $G$ be any graph $L$-cospectral with $T\cup r{K}_1\cup s{K}_2$. By Lemma 2.1, $G$ has $n+r+2s$ vertices, $n-1+s$ edges and $r+s+1$ components. So each component of $G$ is a tree. Suppose that $G=G_0\cup G_1\cup \cdots \cup G_{r+s}$, where $G_i$ is a tree with $n_i$ vertices and $n_0\ge n_1\ge \cdots \ge n_s\ge \cdots \ge n_{r+s}\ge 1$. Since $G$ is $L$-cospectral with $T\cup r{K}_1\cup s{K}_2$, by Lemma 2.3, we get $n_0{n}_1\cdots n_{r+s}=P_L\left(G\right)=n{2}^s$. We claim that $n_s=2$. Suppose not and so $n_s\ge 3$. Therefore, $n_0\ge n_1\ge \cdots \ge n_s\ge 3$ and since $n_{s+1}\ge \cdots \ge n_{r+s}\ge 1$, one may deduce that $n{2}^s=n_0{n}_1\cdots n_{r+s}\ge 3^{s+1}$ or $n{\left(\frac{2}{3}\right)}^s\ge 3$. Now if $s⟶\infty$, then $0\ge 3$, a contradiction. Hence $n_s=2$. By a similar argument one may show that $n_1=n_2=\cdots =n_{s-1}=2$ and so $n_0=n$ and $n_{s+1}=n_{s+2}=\cdots =n_{s+r}=1$. Hence $G=G_0\cup r{K}_1\cup s{K}_2$. Since $G$ and $T\cup r{K}_1\cup s{K}_2$ are $L$-cospectral, $G_0$ and $T$ are $L$-cospectral. Since $T$ is $DLS$, we have $G_0=T$, $G=T\cup r{K}_1\cup s{K}_2$. Hence $T\cup r{K}_1\cup s{K}_2$ is $DLS$. Let $H$ be any graph $Q$-cospectral with $T\cup r{K}_1\cup s{K}_2$. By Lemma 2.1, $H$ has $n+r+2s$ vertices, $n-1+s$ edges and $r+s+1$ bipartite components. So one of the following holds:

(i) $H$ has exactly $r+s+1$ components, and each component of $H$ is a tree.

(ii) $H$ has $r+s+1$ components which are trees, the other components of $H$ are odd unicyclic.

If (i) holds, then $H$ and $T\cup r{K}_1\cup s{K}_2$ are both bipartite, so they are also $L$-cospectral. Since $T\cup r{K}_1\cup s{K}_2$ is $DLS$, we have $H=T\cup r{K}_1\cup s{K}_2$.

If (ii) holds, then by Lemma 2.4, $P_Q\left(H\right)$ is divisible by 4. Since $T$ is a tree of order $n$, by Lemma 2.3, $P_Q\left(H\right)=n{2}^s$ is divisible by 4. Hence $T\cup r{K}_1\cup s{K}_2$ is $DQS$ when $n$ is not divisible by 2 and $s=1$.

Remark 1

Some $DLS$ trees are given in [33–38]. We can obtain $DLS$ ($DQS$) graphs with independent edges and isolated vertices from Theorem 3.1.

Theorem 3.2

Let $G$ be a $DQS$ odd unicyclic graph of order $n\ge 7$. Then $G\cup r{K}_1\cup s{K}_2$ is $DQS$.

Proof

Let $H$ be any graph $Q$-cospectral with $G\cup r{K}_1\cup s{K}_2$. By Lemma 2.4, $P_Q\left(H\right)=4\left(2^s\right)$. By Lemma 2.1, $H$ has $n+r+2s$ vertices, $n+r$ edges and $r+s$ bipartite components. So one of the following holds:

(i) $H$ has exactly $r+s$ components, and each component of $H$ is a tree.

(ii) $H$ has $r+s$ components which are trees, the other components of $H$ are odd unicyclic.

If (i) holds, then we can let $H=H_1\cup \cdots \cup H_{r+s}$, where $H_i$ is a tree with $n_i$ vertices and $n_1\ge \cdots \ge n_{r+s}\ge 1$. Since $P_Q\left(H\right)=4\left(2^s\right)$, by Lemma 2.3, we have $n_1\cdots n_{r+s}=4\left(2^s\right)$, $n_1\le 8$.

Since $G$ contains a cycle, we have $q_1\left(H\right)=q_1\left(G\right)\ge 4$. Let $\Delta \left(H\right)$ be the maximum degree of $H$. If $\Delta \left(H\right)\le 2$, then all components of $H$ are paths, i.e., $q_1\left(H\right)<4$, a contradiction. So $\Delta \left(H\right)>3$. From $n_1\le 8$ and $n_1\cdots n_{r+s}=4\left(2^s\right)=2^{(s+2)}$, we know that $H_1=K_{1,7}$ (without loss of generality), $H_2=\cdots =H_s=K_2$ and $H_{s+1}=\cdots =H_{r+s}=K_1$. Since $H=K_{1,7}\cup (s-1)K_2\cup r{K}_1$ has $n+r+2s$ vertices, we get $n=6$, a contradiction to $n>6$.

If (ii) holds, then we can let $H=U_1\cup \cdots \cup Uc\cup H_1\cup \cdots \cup H_r$, where $U_i$ is odd unicyclic, $H_i$ is a tree with $n_i$ vertices. By Lemmas 2.3 and 2.4, $4\left(2^s\right)=P_Q\left(H\right)=4^c{n}_1\cdots n_r$. So $c=1$, $H_1=\cdots =H_s=K_2$ and $H_{s+1}=\cdots =H_{r+s}=K_1$. Since $H=U_1\cup r{K}_1\cup s{K}_2$ and $G\cup r{K}_1\cup s{K}_2$ are $Q$-cospectral, $U_1$ and $G$ are $Q$-cospectral. Since $G$ is $DQS$, we have $U_1=G$, $H=G\cup r{K}_1\cup s{K}_2.$

Remark 2

Some $DQS$ unicyclic graphs are given in [39–44]. We can obtain $DQS$ graphs with independent edges and isolated vertices from Theorem 3.2.

Theorem 3.3

Let $G$ be a non-bipartite $DQS$ bicyclic graph with $C_4$ as its induced subgraph and $n\ge 5$. Then $G\cup r{K}_1\cup s{K}_2$ is $DQS$.

Proof

Let $H$ be any graph $Q$-cospectral with $G\cup r{K}_1\cup s{K}_2$. By Lemma 2.4, we have $P_Q\left(H\right)=16\left(2^r\right)$. By Lemma 2.1, $H$ has $n+r+2s$ vertices, $n+1+s$ edges and $r+s$ bipartite components, where $n=\left|V\left(G\right)\right|$. So $H$ has at least $r+s-1$ components which are trees. Suppose that $H_1,H_2,\dots ,H_{r+s}$ are $r+s$ bipartite components of $H$, where $H_2,\dots ,H_r$ are trees. If $H_1$ contains an even cycle, then by Lemma 2.3, we have $P_Q\left(H\right)\ge P_Q\left(H_1\right)\ge 16$, and $P_Q\left(H\right)=16\left(2^{s-1}\right)$ if and only if $H=C_4\cup (s-1)K_2\cup r{K}_1$. Since $H$ has $n+r+2s$ vertices, we get $n=2$, a contradiction ($G$ contains $C_4$). Hence $H_1,H_2,\dots ,H_{r+s}$ are trees. Since $H$ has $n+r+2s$ vertices, $n+1+r+2s$ edges and $r+s$ bipartite components, $H$ has a non-bipartite component $H_0$ which is a bicyclic graph. Lemma 2.4 implies that $P_Q\left(H\right)>P_Q\left(H_0\right)>16$, and $P_Q\left(H\right)=16\left(2^s\right)$ if and only if $H=H_0\cup r{K}_1\cup s{K}_2$ and $H_0$ contains $C_4$ as its induced subgraph. By $PQ\left(H\right)=16\left(2^s\right)$, we have $H=H_0\cup r{K}_1\cup s{K}_2$. Since $H$ and $G\cup r{K}_1\cup s{K}_2$ are $Q$-cospectral, $H_0$ and $G$ are $Q$-cospectral. Since $G$ is $DQS$, we have $H_0=G,H=G\cup r{K}_1\cup s{K}_2$. Hence $G\cup r{K}_1\cup s{K}_2$ is $DQS.$

Remark 3

Some $DQS$ bicyclic graphs are given in [45–48]. We can obtain $DQS$ graphs with independent edges and isolated vertices from Theorem 3.3.

Theorem 3.4

Let $G$ be a $DQS$ connected non-bipartite graph with $n\ge 3$ vertices. If $H$ is $Q$-cospectral with $G\cup r{K}_1\cup s{K}_2$, then $H$ is a $DQS$ graph.

Proof

By Lemma 2.1, $H$ has $n+r+2s$ vertices and at least $r+s$ bipartite components. We perform the mathematical induction on $s$.

$H$ has $r+s$ components. Since $H$ has at least $r+s$ bipartite components, each component of $H$ is bipartite. Suppose that $H=H_1\cup \cdots \cup H_{r+s}$, where $H_i$ is a connected bipartite graph with $n_i$ vertices, and $n_1\ge \cdots \ge n_s\ge \cdots \ge n_{r+s}\ge 1$. Since $H$ and $G\cup r{K}_1\cup s{K}_2$ are $Q$-cospectral, by Lemma 2.1, $G$ is a connected non-bipartite graph.

Let $s=1$. For $n\ge 3$, $q_1\left(G\right)\ge 3$, since $G$ has $K_{1,2}$ or $K_3$ as its subgraph. Obviously ${\mathrm{Spec}}_Q\left(H\right)$ has exactly $r+s$ eigenvalues that are zero. We show that if $H$ is $Q$-cospectral with $G\cup r{K}_1\cup K_2$, then $H$ is a $DQS$ graph. First we show that there is no connected graph $Q$-cospectral with ${\mathrm{Spec}}_Q\left(G^{\prime }\right)={\mathrm{Spec}}_Q\left(G\right)\cup \left\{{\left[2\right]}^1\right\}$. In fact we prove that $G^{\prime }$ cannot have 2 as its eigenvalue. Obviously, ${\mathrm{Spec}}_Q\left(H\right)={\mathrm{Spec}}_Q\left(G^{\prime }\right)\cup \left\{{\left[0\right]}^{r+1}\right\}$. But, in this case $\left|E\left(G^{\prime }\right)\right|=\left|E\left(G\right)\right|+1$ and $\left|V\left(G^{\prime }\right)\right|=\left|V\left(G\right)\right|+1$, which means that $G^{\prime }$ must be connected. Otherwise, $G^{\prime }$ contains 0 as its signless eigenvalues, a contradiction. Therefore, $G$ is a proper subgraph of $G^{\prime }$ and so $q_1\left(G^{\prime }\right)\gneqq q_1\left(G\right)\ge 3$ (see Lemma 2.5), a contradiction. Therefore, $G^{\prime }$ cannot have 2 as its eigenvalue. By what was proved one can easily conclude that ${\mathrm{Spec}}_Q\left(H\right)={\mathrm{Spec}}_Q\left(G\right)\cup {\mathrm{Spec}}_Q\left(K_2\right)\cup {\mathrm{Spec}}_Q\left(r{K}_1\right)$, since $G$ is not a bipartite graph and so has not $0$ as an its signless Laplacian eigenvalue. Therefore, $H=G\cup K_2\cup r{K}_1$.

Now, let the theorem be true for $s$; that is, if ${\mathrm{Spec}}_Q\left(G_1\right)={\mathrm{Spec}}_Q\left(G\right)\cup {\mathrm{Spec}}_Q(r{K}_1\cup s{K}_2)$, then $G_1=G\cup r{K}_1\cup s{K}_2$. We show that it follows from ${\mathrm{Spec}}_Q\left(K\right)={\mathrm{Spec}}_Q\left(G\right)\cup {\mathrm{Spec}}_Q(r{K}_1\cup (s+1)K_2)$ that $K=G\cup r{K}_1\cup (s+1)K_2$. Obviously, $K$ has $2$ vertices, one edge and one bipartite component more than $G_1$. So, we must have $K=G_1\cup K_2$.

Remark 4

In the following results graph $G$ in $G\cup r{K}_1\cup s{K}_2$ is a connected non-bipartite.

Corollary 3.1

The graph $K_n\cup r{K}_1\cup s{K}_2$ is $DQS$.

Proof

From [6] (Proposition 7), if $n=1,2$, then $K_n\cup r{K}_1\cup s{K}_2$ is $DQS$. For $n\ge 3$, by Theorem 3.4 the result follows.

In [49], Cámara and Haemers proved that a graph obtained from $K_n$ by deleting a matching is $DAS$. In [50], it have been shown that this graph is also $DQS$.

Corollary 3.2

Let $G$ be the graph obtained from $K_n$ by deleting a matching. Then $G\cup r{K}_1\cup s{K}_2$ is $DQS$.

Proof

From [6] (Proposition 7), if $n=1,2$, then $K_n\cup r{K}_1\cup s{K}_2$ is $DQS$. For $n\ge 3$, by Theorem 3.4 the result follows.

A regular graph is $DQS$ if and only if it is $DAS$ [6]. It is known that a $k$-regular graph of order $n$ is $DAS$ when $k=0,1,2,n-1,n-2,n-3$ [17]. Hence a $k$-regular graph of order $n$ is $DQS$ when $k=0,1,2,n-1,n-2,n-3$.

Corollary 3.3

Let $G$ be a connected $(n-2)$-regular graph of order $n$. Then $G\cup r{K}_1\cup s{K}_2$ is $DQS$.

Corollary 3.4

Let $G$ be a connected $(n-3)$-regular graph of order $n$. Then $G\cup r{K}_1\cup s{K}_2$ is $DQS$.

Corollary 3.5

Let $G$ be a connected $(n-4)$-regular $DAS$ graph. Then $G\cup r{K}_1\cup s{K}_2$ is $DQS$.

Remark 5

Some $3$-regular $DAS$ graphs are given in [6,51]. We can obtain $DQS$ graphs with independent edges and isolated vertices and isolated vertices from Corollary 3.4.

Corollary 3.6

Let $F_n$ denote the friendship graph and $G$ be $Q$-spectral with $F_n$, then $G\cup r{K}_1\cup s{K}_2$ is $DQS$.

Proof

It is well-known that $F_n$ is $DQS$. By Theorem 3.4 the proof is completed.