The spectral determinations of connected multicone graphs K_w ▽ mCP(n)

1.   Introduction

All graphs which are considered here are simple and undirected. Let $G$ be a graph of order $n = |V(G)|$ and size $m = |E(G)|$. For $v \in V(G)$, the degree of $v$, denoted by $d_G(v)$, is the number of edges incident to $v$. Let $G$ be a simple graph on $n$ vertices and $A(G) = (a_{ij})$ be its adjacency matrix, that is, $a_{ij}$ equals 1 if $v_i$ is adjacent to $v_j$ and equals 0, otherwise. All terminology and notations on graphs not defined here, may be found in ^{[1,2,3,4,5,18,19,34]}. We show $n$ disjoint copies of a graph $\Gamma$ by $n\Gamma$. For two graphs $G_1$ and $G_2$ with disjoint vertex sets $V (G_1)$ and $V (G_2)$ and disjoint edge sets $E(G_1)$ and $E(G_2)$ the disjoint union of $G_1$ and $G_2$ is the graph $G = G_1 \cup G_2$ with the vertex set $V (G_1) \cup V (G_2)$ and the edge set $E(G_1) \cup E(G_2)$. The join $G\bigtriangledown H$ of simple undirected graphs $G$ and $H$ is the graph with the vertex set $V (G \bigtriangledown H) = V (G) \cup V (H)$ and the edge set $E(G \bigtriangledown H) = E(G) \cup E(H) \cup\left\{ {uv|\, u \in \, V(G), \, v \in \, V(H)} \right\}$. For a graph $G$, let $D(G) = diag(d_1, d_2, ..., d_n)$ be the diagonal matrix of vertex degrees. The matrices $Q(G) = D(G) + A(G)$ and $L(G) = D(G) - A(G)$ are called the signless Laplacian matrix and Laplacian matrix of $G$, respectively. We denote the characteristic polynomial $det (\lambda I - A)$ of $G$ by $P_G(\lambda)$. The adjacency spectrum of $G$, denoted by ${\rm{Spec}}_{A}(G)$, is the multiset of eigenvalues of $A(G)$. Since $A(G)$ is symmetric, its eigenvalues are real. The adjacency spectrum of the graph $G$ consists of the adjacency eigenvalues (together with their multiplicities), and the Laplacian spectrum of the graph $G$ consists of the Laplacian eigenvalues (together with their multiplicities). Two graphs $G$ and $H$ are said to be $A$-cospectral ($L$-cospectral) if they have equal adjacency (Laplacian) spectrum. The adjacency spectrum and the Laplacian spectrum of a graph $G$ is denoted by ${\rm{Spec}}_{A}(G)$ and ${\rm{Spec}}_{L}(G)$, respectively. Two graphs with the same spectrum are called cospectral. A graph $G$ is said to be a $DAS$-graph (a $DLS$-graph) if there is no other non-isomorphic graph $A$-cospectral ($L$-cospectral) to it. For a $DQS$-graph (determined by signless Laplacian spectrum) the definition is similar.

In general, the spectrum of a graph does not determine the graph and the question "Which graphs are determined by their spectrum?" ^[29] remains a difficult problem. For the background and some known results about this problem and related topics, we refer the readers to ^[29] and references therein. In ^[29] it is conjectured that almost all graphs are determined by their spectra. Nevertheless, the set of graphs which are known to be $DAS$ (or $DLS$) is too small and therefore it would be interesting to find more examples of these graphs. The authors ^[31] characterized special classes of connected multicone graphs. They also conjectured that friendship graphs are $DAS$-graphs. Finally, in ^[21] this conjecture for $n\neq 16$ were proved. Abdian and Mirafzal ^[1] characterized new classes of multicone graphs. For seeing some graphs and multicone graphs which have been characterized so far we refer the reader to ^{[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,24,25,26]}.

We think that in ^[31] there are some gaps. In ^[31], the authors conjectured that the minimum degree of graphs $A$-cospctral with a friendship graph is $2$ (see Conjecture 1). Put simply, they could not determine the minimum degree of graphs $A$-cospectral with a (bidegreed) multicone graph (Conjecture 1). Hence, by their techniques ^[31] cannot characterize new classes of multicone graphs that we have presented in this study. Conjectures (Conjectures 1 and 2) which had been proposed by the authors ^[31] are not valid and there is a counterexample for any of them (for further information see the first paragraph after Corollary 2 of ^[22]). In Theorem 3 (ii) of ^[31] first the minimum degree of a graph $A$-cospectral to a graph belonging to $\beta(n-1, \delta)$ (classes of bidegreed graphs with degree sequence $\delta$ and $n-1$, where $n$ denotes the number of vertices) must be determined, since in general determining of the minimum degree of a graph by its spectrum is impossible. Therefore, this theorem without knowing and finding the minimum degree of a graph $A$-cospectral with one of graphs $\beta(n-1, \delta)$ will not effective and useful.

In this paper, we present new classes of multicone graphs that are both $DAS$ and $DLS$-graphs.

2.   Preliminaries

In this section we state some results which are needed in the next sections.

Lemma 2.1. ^{[1,2,3,4,6,19,24,29]} Let $G$ be a graph. For the adjacency matrix and Laplacian matrix, the following can be obtained from the spectrum:

(i) The number of vertices,

(ii) The number of edges.

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

(iii) The 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 number of spanning trees,

(vii) The number of components,

(viii) The sum of squares of degrees of vertices.

Theorem 2.1. ^{[1,2,3,4,7,22,24]} If $G_1$ is $r_1$-regular with $n_1$ vertices, and $G_2$ is $r_2$-regular with $n_2$ vertices, then the characteristic polynomial of the join $G_1\bigtriangledown G_2$ is given by:

Theorem 2.2. ^[1,2,3,4,24] Let $G$ be a graph on $n$ vertices. Then $n$ is one of the Laplacian eigenvalue of $G$ if and only if $G$ is the join of two graphs.

Theorem 2.3. ^[1,2,3,4,24] Let $G$ and $H$ be two graphs with Laplacian spectrum $\lambda_1\ge\lambda_2\ge...\ge\lambda_n$ and $\mu_1\ge\mu_2\ge...\ge\mu_m$, respectively. Then Laplacian spectra of $\overline{G}\ $ and $G \bigtriangledown H$ are $n -\mathop \lambda \nolimits_1, n - \mathop \lambda \nolimits_2, ..., n - \mathop \lambda \nolimits_{n - 1}, 0$ and $n + m, m + \mathop \lambda \nolimits_1, ..., m + \mathop \lambda \nolimits_{n - 1}, n + \mathop \mu \nolimits_1, ..., n + \mathop \mu \nolimits_{m - 1}, 0$, respectively.

Theorem 2.4. ^[1,24,28,33] A graph has exactly one positive eigenvalue if and only if it is a complete multipartite graph with possibly some isolated vertices. The spectrum $K_{n_1. \cdots, n_p}$ consists of the spectral radius (the largest eigenvalue) $\lambda_1$ determined byfrom the equation $\sum\limits_{i = 1}^p {\dfrac{{{n_i}}}{{\lambda + {n_i}}}} = 1$, eigenvalue 0 with the multiplicity $n-p$ and $p-1$ eigenvalues situated in the intervales $[-n_p, -n_{p-1}], \cdots, [-n_2, -n_1]$.

Theorem 2.5. ^[18] If $\Gamma$ is an $r$-regular graph with eigenvalues $\lambda_1 ( = r), \lambda_2, ..., \lambda_n$, then $n-1-\lambda_1, -1-\lambda_2, ..., -1-\lambda_n$ are the eigenvalues of the complement $\overline{\Gamma}$ of $\Gamma$, i.e.,

Theorem 2.6. ^[22] Let $G$ be a graph of order $n$, the complement of $G$, $\overline{G}$, has the characteristic polynomial

where $m$ and $\beta _i$ are the number of distinct eigenvalues and the main angles (see ^[27]) of graph $G$, respectively.

Theorem 2.7. ^[22] If $H$ is a proper subetaaph of connected graph $G$, then

Theorem 2.8. ^[30] Let $G$ be a disconnected graph that is a $DLS$-graph. Then $K_1\bigtriangledown G$, is also a $DLS$-graph

The rest of the paper is organized as follows. In Section 3, we characterize graphs that are determined by their adjacency spectrum. In Section 4, we prove that graph $L$-cospectral to one of these graphs is determined by their Laplacian spectra. In Section 5, we prove that any graph $A$-cospectral ($L$-cospectral) to one of these graphs must be perfect. In Section 6, we review what were said in the previous sections and finally we propose two conjectures for further research.

3.   Main Results

3.1.   Connected graphs $A$-cospectral to a multicone graph $K_w\bigtriangledown mCP(n)$

Proposition 3.1. Let $G$ be a graph $A$-cospectral to the multicone graph $K_w\bigtriangledown mCP(n)$. Then ${\rm{Spec}}_{A}(G) = \left\{ {{{\left[ {\dfrac{{\Omega + \sqrt {{\Omega ^2} - 4\Psi} }}{2}} \right]}^1}, {{\left[ { - 1} \right]}^{w - 1}}, {{\left[ { - 2} \right]}^{(n - 1)m}}, {{\left[ 0 \right]}^{nm}}, {{\left[ 2n-2 \right]}^{m-1}}, {{\left[ {\dfrac{{\Omega - \sqrt {{\Omega ^2} - 4\Psi} }}{2}} \right]}^1}} \right\}$, where $\Omega = 2n+w-3$ and $\Psi = (w - 1)(2n - 2) - 2nmw$.

Proof. Obviously, ${\rm{Spec}}_{A}(mCP(n)) = \left\{ {{{\left[ {2n - 2} \right]}^m}, {{\left[ 0 \right]}^{nm}}, {{\left[ { - 2} \right]}^{(n - 1)m}}} \right\}$ (see ^[22]). Put, $y_1 = w-1$, $y_2 = -1$, $y_3 = 2n-2$, $y_4 = 0$, $y_5 = -2$, $D = 2nmw$ and $P_{A(K_w\bigtriangledown mCP(n)}(y) = P_{A(G)}(y)$. Now, it follows from Theorem 2.1 that $P_{A(G)}(y) = \dfrac{(y-y_1)(y-y_2)^{w-1}(y-y_3)^m(y-y_4)^{mn}(y-y_5)^{(n-1)m}}{(y-y_1)(y-y_3)}((y-y_1)(y-y_3)-D)$. Now, the eigenvalues are the roots of the above equation.

Lemma 3.1. Let $G$ be $A$-cospectral to the multicone graph $K_w\bigtriangledown mCP(n)$. Then $G$ is a $DAS$-graph.

Proof. It is clear that $P_{A(G)}(x) = P_{A(K_w\bigtriangledown mCP(n))}(x)$. It follows from Theorem 2.6 that $P_{A(\overline{G})}(x)$=$(-1)^{2mn+w}P_{A(G)}(-x-1)(1-(2mn+w)\sum\limits_{i = 1}^6 {\dfrac{{{\beta _i}^2}}{{x + 1 + {\mu _i}}}}$=$(-1)^{2mn+w}P_{A(K_w\bigtriangledown mCP(n))}(-x-1)(1-(2mn+w)\sum\limits_{i = 1}^6 {\dfrac{{{\beta _i}^2}}{{x + 1 + {\mu _i}}}})$=$P_{A(\overline{K_w\bigtriangledown mCP(n)})}(x)$. Hence $P_{A(\overline{G})}(x) = P_{A(\overline{K_w\bigtriangledown mCP(n)})}(x)$. Therefore, ${\rm{Spec}}_{A}(\overline{G}) = {\rm{Spec}}_{A}(\overline{K_w\bigtriangledown mCP(n)})$. By Theorem 2.5 ${\rm{Spec}}_{A}(\overline{G}) =$ ${\rm{Spec}}_{A}(\overline{K_w\bigtriangledown mCP(n)}) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{m - 1}}, \, {{\left[ { - 1} \right]}^{mn}}, \, {{\left[ 1 \right]}^{(n - 1)m}}, \, {{\left[ 0 \right]}^w}} \right\}$.

Consider the exponents of $a$, $b$, $c$ and $d$ with $1\leq a\leq m-1$, $1\leq b\leq mn$, $1\leq c\leq (n-1)m$ and $1\leq d\leq w$.

Obviously, any graph with two distinct eigenvalues is a complete graph with at least two vertices. Also, note that if a graph has at least an edge, then the largest eigenvalue is always positive and the smallest eigenvalue is always negative. A graph with no edges only has 0 as its eigenvalue. In addition, any graph with at least an edge has $K_2$ as its subetaaph. Consider the following cases:

Case 1. $\overline{G}$ is connected. Obviously, this case cannot happen. Consider ${\rm{Spec}}_{A}(H) =$ $\left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{m - 1}}, \, {{\left[ { - 1} \right]}^{mn}}, \, {{\left[ 1 \right]}^{(n - 1)m}}, \, {{\left[ 0 \right]}^w}} \right\}$ and ${\rm{Spec}}_{A}(\overline{mCP(n)}) =$ $\left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{m - 1}}, \, {{\left[ { - 1} \right]}^{mn}}, \, {{\left[ 1 \right]}^{(n - 1)m}}} \right\}$. Clearly, $H$ has $w$ vertices more than $\overline{mCP(n)}$. On the other hand, the number of edges $H$ and $\overline{mCP(n)}$ are the same. Consequently by a simple induction on $w$ we prove that $H = wK_1\cup \overline{mCP(n)}$. For $w = 1$, it is easy to see that $H = \overline{mCP(n)}\cup K_1$, since $H$ has a vertex more than $\overline{mCP(n)}$ and the number of their edges are the same (Note that $\overline{mCP(n)}$ is a $DAS$-graph). Let the problem is true for $w$; that is if ${\rm{Spec}}_{A}(H_1) = {\rm{Spec}}_{A}(H)$, then $H_1 = wK_1\cup \overline{mCP(n)}$, where $H_1$ is an arbitrary graph $A$-cospectral with $H$. We prove that the problem for $w+1$. In other words, if ${\rm{Spec}}_{A}(H_2) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{m - 1}}, \, {{\left[ { - 1} \right]}^{mn}}, \, {{\left[ 1 \right]}^{(n - 1)m}}, \, {{\left[ 0 \right]}^{w+1}}} \right\}$, then $H_2 = (w+1)K_1\cup \overline{mCP(n)}$. Obviously, $H_2$ has $1$ vertex more than $H_1$. On the other hand, the number of edges $H_1$ and $H_2$ are the same. Therefore, $H_2 = H_1\cup K_1$. Now, the induction hypothesis completes the proof.

In the following we show that $\overline{mCP(n)}$ and $wK_1$ are only subetaaphs of $\overline{G}$. To put that another way, $\overline{G} = \overline{mCP(n)}\cup wK_1$.

Case 2. $\overline{G}$ is disconnected; that is $\overline{G} = H_1\cup \cdots \cup H_n$. Obviously, ${\rm{Spec}}_{A}(\overline{G}) = {\rm{Spec}}_{A}(H_1)\cup \cdots\cup {\rm{Spec}}_{A}(H_n)$. Consider the following subcases:

1. If proper subetaaph $H_1$ of $\overline{G}$ has two distinct eigenvalues.

(a) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 1} \right]}^{b}}} \right\}$.

Since the summation of the eigenvalues of a graph is always zero, so $2mn-2n+1-b = 0$, which means that $b = 2mn-2n+1$. On the other hand, since $H_1$ has two distinct eigenvalues, so it is a disjoint union of complete graphs on the same vertices; i.e., $b = 1$ or $2mn-2n+1 = 1$. Therefore, $2mn = 2n$ or $m = 1$. This means that $H_1 = K_2 = \overline{CP(1)}$.

(b) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{a}}} \right\}$. Since $2mn-2n+1+a(-2n+1) = 0$, so $a = \dfrac{2mn-2n+1}{2n-1}\leq m-1\leq nm$ or $2mn-2n+1\leq 2nm-nm$. Therefore, $-2n+1\leq -nm$, for $m\geq 2$ we get a contradiction. If $m = 1$, then $a = 0$, a contradiction.

(c) ${\rm{Spec}}_{A}(H_1) = \left\{ {\, {{\left[ { - 1} \right]}^{b}}, \, {{\left[ 1 \right]}^{c}}} \right\}$. If $H_1$ is a connected graph, then by the Perron-Frobenius theorem $c = b = 1$ and so $H_1 = K_2 = \overline{CP(1)} = \overline{1CP(1)}$. If $H_1$ is disconnected, then $H_1 = cK_2 = \overline{CP(c)} = \overline{1CP(c)}$, where $b = c\geq 2$.

(d) ${\rm{Spec}}_{A}(H_1) = \left\{ {\, {{\left[ { - 2n + 1} \right]}^{a}}, \, {{\left[ 1 \right]}^{c}}} \right\}$. By Perron-Frobenius theorem $c = 1$. Obviously, $(-2n+1)a = -1$ or $a = \dfrac{1}{2n-1}$. Clearly, $n = 1$ or $H_1 = K_2 = \overline{CP(1)} = \overline{1CP(1)}$.

2. If proper subetaaph $H_1$ of $\overline{G}$ has three distinct eigenvalues. By Theorem 2.4 any graph with exactly one positive eigenvalue is a multipartite graph with possibly some isolated vertices.

(a) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ {0} \right]}^{d}}, \, {{\left[ { - 1} \right]}^{b}}} \right\}$. Since $2mn-2n+1-b = 0$, so $b = 2mn-2n+1\leq mn$ or $mn-2n+1\leq 0$. It is clear that for $m\geq 2$ we have a contradiction. If $m = 1$, then $b = 1$ and so $H_1 = K_2 = \overline{1CP(1)}$, a contradiction.

(b) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{a}}, \, {{\left[ {0} \right]}^{d}}} \right\}$. Similar Subcase 1 (b) we get a contradiction.

(c) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{a}}, \, {{\left[ { - 1} \right]}^{b}}} \right\}$, a contradiction, since any multipartite graph consists of the eigenvalue 0.

(d) ${\rm{Spec}}_{A}(H_1) = \left\{ {\, {{\left[ { - 1} \right]}^{b}}, \, {{\left[ 1 \right]}^{c}}, \, {{\left[ 0 \right]}^d}} \right\}$. If $H$ is a connected graph, then $b = c = 1$ and so $b+c = 2m(H_1)$ or $m(H_1) = 1$. This means that $H_1 = K_2\cup dK_1$, a contradiction, since any multipartite graph is a connected graph.

(e) ${\rm{Spec}}_{A}(H_1) = \left\{ {\, {{\left[ { - 1} \right]}^{b}}, \, {{\left[ 1 \right]}^{c}}, \, \, {{\left[ { - 2n + 1} \right]}^{a}}} \right\}$. Obviously, $(2n - 1)a = b-c$. By the Perron-Frobenius theorem $c = 1$. By Theorem 2.4 $H_1$ is a multipartite complete graph and as a result it has 0 as its eigenvalue and so we get a contradiction.

(f) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 1} \right]}^{b}}}, \, {{\left[ { 1} \right]}^{c}} \right\}$. Clearly, $2mn-2n+1 = b-c\leq b+c\leq mn+m-1$ or $mn-2n\leq -2$. For $m\geq 2$ we get a contradiction. If $m = 1$, then we have not three distinct eigenvalues, a contradiction.

3. If proper subetaaph $H_1$ of $\overline{G}$ has four distinct eigenvalues.

(a) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ {0} \right]}^{d}}, \, {{\left[ { - 1} \right]}^{b}}}, \, {{\left[ {1} \right]}^{c}} \right\}$. The proof is similar to Subcase 2 (f).

(b) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^1}, \, {{\left[ { - 2n + 1} \right]}^{a}}, \, {{\left[ { - 1} \right]}^{b}}}, \, {{\left[ { 1} \right]}^{c}} \right\}$. It is clear that $a = m-1$, $b = mn$ and $c = (n-1)m$. In this case $H = \overline{mCP(n)}$.

(c) ${\rm{Spec}}_{A}(H_1) = \left\{{\left[ {0} \right]}^{a}, \, {{\left[ { - 1} \right]}^{b}}, \, {{\left[ { 1} \right]}^{c}}, \, {{\left[ { - 2n + 1} \right]}^{a}} \right\}$. Clearly $c-b = (2n-1)a$ and so $1 = b+(2n-1)a$. Since $b\geq 1$ thus $b = 1$ and $(2n-1)a = 0$ or $n = \dfrac{1}{2}$, which is impossible.

4. If proper subetaaph $H_1$ of $\overline{G}$ has five distinct eigenvalues.

(a) ${\rm{Spec}}_{A}(H_1) = \left\{ {{{\left[ {2mn - 2n + 1} \right]}^{1}}, \, {{\left[ { - 2n + 1} \right]}^{a}}, \, {{\left[ { - 1} \right]}^{b}}, \, {{\left[ 1 \right]}^{c}}, \, {{\left[ 0 \right]}^{d}}} \right\}$. It is clear that there is no connected graph with this spectrum, otherwise by Subcase 3 (b) $\overline{mCP(n)}$ is a proper subetaaph of $H_1$ and so by Theorem 2.7 $2mn - 2n + 1 = \varrho(H_1) > \varrho(\overline{mCP(n)}) = 2mn - 2n + 1$, which is impossible.

By what was proved it is easy to see that $H_1 = \overline{mCP(n)}$ and so $\overline{G} = wK_1\cup \overline{mCP(n)}$ or $G = K_w\bigtriangledown mCP(n)$.

Corollary 3.1. Any graph $A$-cospectral to a multicone graph $K_w\bigtriangledown mCP(2) = K_w\bigtriangledown mC_4$ is a $DAS$-graph.

In the following lemma, we show that multicone graphs $K_w\bigtriangledown mCP(n)$ are $DLS$-graphs.

4.   Graphs $L$-cospectral to a multicone graph $K_w\bigtriangledown mCP(n)$

Theorem 4.1. If ${\rm{Spec}}_{L}(G) = {\rm{Spec}}_{L}(K_w\bigtriangledown mCP(n))$, then $G\cong K_w\bigtriangledown mCP(n)$.

Proof. We solve the problem by induction on $w$. If $w = m = 1$, then by Theorems 2.2 and 2.3 the proof is clear. If $w = 1$ and $m\geq 2$, then by Theorem 2.8 the proof is straightforward. Let the problem be true for $w$; that is, if ${\rm{Spec}}_{L}(G_1) = {\rm{Spec}}_{L}(K_w\bigtriangledown mCP(n))$, then $G_1\cong K_w\bigtriangledown mCP(n)$, where $G_1$ is a graph. We show that ${\rm{Spec}}_{L}(G) = {\rm{Spec}}_{L}(K_{w+1}\bigtriangledown mCP(n))$ implies that $G \cong K_{w+1}\bigtriangledown mCP(n)$. It follows from Theorem 2.2 that $G = H_1\bigtriangledown H_2$ and so ${\rm{Spec}}_{L}(H_1\bigtriangledown H_2) = {\rm{Spec}}_{L}(K_1\bigtriangledown(K_{w}\bigtriangledown mCP(n)))$. By Theorem 2.3 ${\rm{Spec}}_{L}(H_2) = {\rm{Spec}}_{L}(K_w\bigtriangledown mCP(n))$ and $H_1 = K_1$. By the induction hypothesis $H_2 = K_w\bigtriangledown mCP(n)$ and so $G = H_1\bigtriangledown H_2 = K_1\bigtriangledown(K_w\bigtriangledown mCP(n)) = K_{w+1}\bigtriangledown mCP(n))$. The proof is complete.

Corollary 4.1. Any graph $L$-cospectral to the multicone graph $K_w\bigtriangledown mCP(2) = K_w\bigtriangledown mC_4$ is a $DLS$-graph.

In the following, we show that any graph $A$-cospectral and also $L$-cospectral to the multicone graph $K_w\bigtriangledown mCP(n)$ is perfect.

5.   Some graphical properties about multicone graphs $K_w\bigtriangledown mCP(n)$

Suppose $\chi(G)$ and $\omega(G)$ are chromatic number and clique number of graph $G$, respectively. A graph is perfect if $\chi(H) = \omega(H)$ for every induced subetaaph $H$ of $G$. It is proved that a graph $G$ is perfect if and only if $G$ is Berge; that is, it contains no odd hole or antihole as induced subetaaph, where odd hole and antihole are odd cycle, $C_m$ for $m\ge 5$, and its complement, respectively. Also, in $1972$ Lovász proved that, a graph is perfect if and only if its complement is perfect(see ^[1,17]).

Theorem 5.1. Let graph $G$ be $A$-cospectral to a multicone graph $K_w\bigtriangledown mCP(n)$. Then $G$ and $\overline{G}$ are perfect.

Proof. It is quite clear that $G$ cannot consist of an odd hole of order greater than or equal to five as an induced subetaaph. We show that $G$ contains no odd antihole of order greater than or equal to five as an induced subetaaph. By contrary, we suppose that $G$ contains $\overline{C_k}$ as an induced subetaaph, where $k$ is odd and $k\geq 5$. Hence $\overline{G} = wK_1\cup \overline{mCP(n)}$ must consists of $C_k$ as an induced subetaaph. In other words, $\overline{mCP(n)} = \underbrace {n{K_2}\bigtriangledown.\, .\, .\, \bigtriangledown n{K_2}}_{m\, times}$ must consists of $C_k$ as an induced subetaaph. This is obviously a contradiction.

Theorem 5.2. Let ${\rm{Spec}}_{L}(G) = {\rm{Spec}}_{L}(K_w\bigtriangledown mCP(n))$. Then $G$ and $\overline{G}$ are perfect.

Proof. The proof is in the same way of Theorem 5.1.

In the following, we pose two conjectures.

6.   Final remarks and open problems

In this paper, we have shown any graph $A$-cospectral to a multicone graph $K_w\bigtriangledown mCP(n)$ is DS with respect to its spectra. Also, we have shown in specialcases the complement of these graphs are DS. In addition, we have proved any graph $A$-cospectral ($L$-cospectral) to one of these graphs is perfect. Hence we pose two conjectures.

Conjecture 1. Any graph $A$-cospectral to a complement of multicone graph $K_w\bigtriangledown mCP(n)$ is a $DAS$-graph.

Conjecture 2. Multicone graphs $K_w\bigtriangledown mCP(n)$ are $DQS$-graphs.

Conflict of interest

The authors declare that there is no conflict of interest.