The spectral determination of the connected multicone graphs

Abstract

The main goal of the paper is to answer an unsolved problem. A multicone graph is defined to be the join of a clique and a regular graph, and a wheel as the join of a vertex and a cycle. In this study, we present new classes of multicone graphs that are natural generalizations of wheel graphs and we show that they are determined by their adjacency spectra as well as their Laplacian spectra. We also show that the complements of some of these graphs are determined by their adjacency spectra. In addition, we give a necessary and sufficient condition for perfect graphs cospectral with some of the graphs investigated in the paper. Finally, we conclude with two problems for further study.

Keywords:

• Adjacency spectrum
• Laplacian spectrum
• DS graph
• multicone graph
• wheel graph

MSC(2010):

• 05C50

1. Introduction

In [25] and [43], it is shown that all wheel graphs are determined by both their signless Laplacian and their Laplacian spectra, respectively, except for the wheel graph of order seven. However, wheel graphs have not been characterized with respect to their adjacency spectra. Hence, the question “When are wheel graphs determined by their adjacency spectra?” is still unsolved. So any findings about the determination of the wheel graphs with respect to their adjacency spectra can be interesting.

All graphs that we consider are simple and undirected, and usually they will be connected. Unless otherwise indicated, n will denote the number of vertices and m the number of edges in the graph $G=(V,E)$ (n is sometimes called the order of G) and the vertex set $V=V(G)$ will be $\left\{v_1,v_2,\dots ,v_n\right\}$ and edge set E(G). Concepts not defined here can be found in the books [17, 20, 24]. The complement of a graph G is denoted by $\overline{G}.$ The graph consisting of k disjoint copies of graph G will be denoted by kG, and consistent with this notation, the disjoint union of two graphs G and H will be denoted G + H. The join $G\nabla H$ of two graphs G and H is the graph obtained from their disjoint union G + H and connecting every vertex of G to every vertex of H. We say that a graph G is r-regular if the degree of every vertex is r and (r, s)-bi-degreed if it is not regular but every vertex has degree r or s. The cone over a graph G is the join of a single vertex with G, that is, $K_1\nabla G.$

Let $\mathbf{A}(G)$ be the (0, 1)-adjacency matrix of G and let $\mathbf{D}(G)$ be the diagonal matrix with the i’th diagonal entry being the degree d_i of the vertex v_i. The matrix $\mathbf{L}(G)=\mathbf{D}(G)-\mathbf{A}(G)$ is called the Laplacian matrix of G. Since both matrices $\mathbf{A}(G)$ and $\mathbf{L}(G)$ are real and symmetric, their eigenvalues are all real. Let ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_n$ be the eigenvalues of $\mathbf{A}(G)$ and ${\mu }_1\ge {\mu }_2\ge \dots \ge {\mu }_n(=0)$ the eigenvalues of $\mathbf{L}(G).$ The spectral radius of G is the largest eigenvalue of its adjacency matrix is denoted by $\rho (G).$ The adjacency spectrum ${\mathrm{Spec}}_A(G)$ of G consists of the adjacency eigenvalues (together with their multiplicities), and similarly the Laplacian spectrum ${\mathrm{Spec}}_L(G)$ consists of the Laplacian eigenvalues (together with their multiplicities). We are interested in connected graphs for which there are no other (non-isomorphic) connected graphs with the same spectrum of a given type. Such graphs are said to be determined by that spectrum, denoted DAS for the adjacency spectrum, DLS and DQS for the Laplacian spectrum and signless Laplacian spectrum, respectively.

Examples of cospectral non-isomorphic graphs have been constructed by interesting techniques such as Seidel switching, Godsil-McKay switching, the Schwenk method, and the Sunada method. For more information, see [38, 39] and the references cited there. Only a few graphs with very special structures have been found to be determined by their spectra (DS, for short) (see [1–16, 22, 26–30, 32, 34–36, 38, 39] and the references cited therein). Van Dam and Haemers [38] 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 still small, and so discovering new classes of such graphs would be significant. The problem of characterizing DS graphs goes back about half a century originated in chemistry [22, 31]. For more on the background of the question” Which graphs are determined by their spectrum?”, we refer to [38]. The spectral characterization of certain multicone graphs was explored by Wang, Zhao and Huang [42], who asserted that friendship graphs F_n (certain special classes of multicone graphs) are adjacency-spectrum determined. In addition, Wang, Belardo, Huang and Borovićanin [40] proposed such conjecture on the adjacency spectrum of F_n. This conjecture inspired activity on the spectral characterization of this family of graphs. Finally, Cioabä and et al. [19] proved that if $n\ne 16,$ then the friendship graph F_n is DS with respect to its adjacency spectrum. Abdian and Mirafzal [11] characterized new classes of multicone graphs that are DAS. Abdian [1] characterized two classes of multicone graphs and proved that the join of an arbitrary complete graph and a generalized quadrangle graph GQ(2, 1) or GQ(2, 2) is both DAS and DLS. In the same paper, the author proposed four conjectures about the adjacency spectrum of graph complements and the signless Laplacian spectrum of these multicone graphs. In [2] and [3], it was shown that the multicone graph $K_w\nabla G$ for G being the Paley graph P₁₇ of order 17, the Schläfli graph S, or the line graph L(P) of the Petersen graph, is both DAS and DLS, and it is conjectured that these multicone graphs are also DQS. He also proposed three conjectures about the signless Laplacian spectrum and the complement spectrum of these multicone graphs. For getting further information related to this topic, see [4, 12].

We believe that there are some gaps in the proofs in [42]. There it was conjectured that if a graph is cospectral to a friendship graph, then it has minimum degree 2 (see Conjecture 1). In other words, they could not determine the minimum degree of graphs cospectral to a (bi-degreed) multicone graph (see Conjecture 1). Hence, one cannot use their techniques ([42]) to characterize new classes of multicone graphs, which is what we want to do here. Conjectures 1 and 2 of Wang, Zhao and Huang [42] are not true, and there are counterexamples for them (see the first paragraph after Corollary 2 of [19]). In Theorem 3 (ii) of [42] first the minimum degree of a graph cospectral to a graph belonging to $\beta (n-1,\delta )$ (classes of bi-degreed graphs with degree sequence δ and $n-1,$ where n denotes the number of vertices) must be determined, since in general the minimum degree of a graph cannot be determined by its spectrum. Therefore, we think that theorem without knowing the minimum degree of a graph cospectral with one of graphs $\beta (n-1,\delta )$ will not be effective or useful. For some multicone graphs which have been characterized, see [1–4, 8, 9, 11–13, 28, 29, 34].

In this paper, we present some techniques which enable us to characterize graphs that are DAS and DLS.

This paper is organized as follows. In Section 2, we review some basic information and preliminaries. In Section 3, we present some new classes of graphs that are either bi-degreed or regular with respect to their adjacency spectrum. In Subsection 3.1, we prove that any graph cospectral with one of these graphs is determined by its adjacency spectrum. In Subsection 3.2, we show that the complements of some classes of these graphs are determined by their adjacency spectrum (DAS). In Section 4, we prove that these graphs are also spectrum determined with respect to their Laplacian spectrum (DLS). In Subsection 4.1, we show that any graph cospectral with special classes of these graphs must be perfect. In Section 5, we propose two conjectures for further research.

2. Preliminaries

In this section, we present some results which will play an important role throughout this paper.

Lemma 2.1

([12, 13, 20]). The following can be obtained from the adjacency spectrum and Laplacian spectrum of a graph $G$:

From either spectrum,

(i) the number of vertices,

(ii) the number of edges.

From the adjacency spectrum,

(iii) the number of closed walks of any length,

(iv)whether G is regular or not, and if it is, the common degree,

(v) whether G is bipartite or not.

From the Laplacian spectrum,

(vi) the number of spanning trees,

(vii) the number of components,

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

In what follows, $P_G(y)$ denotes the characteristic polynomial of graph G.

Theorem 2.1

([20, 42]). If for i = 1, 2, G_i has order n_i and is r_i-regular, then the characteristic polynomial of the join $G_1\nabla G_2$ is $$P_{G_1\nabla G_2}(y)=\frac{P_{G_1}(y)P_{G_2}(y)}{(y-r_1)(y-r_2)}((y-r_1)(y-r_2)-n_1{n}_2).$$

Theorem 2.2

([23, 42]). Let G be a graph with n vertices, m edges, minimum degree δ, and spectral radius $\rho (G)$. Then $$\rho (G)\le \frac{\delta -1}{2}+\sqrt{2m-n\delta +\frac{{(\delta +1)}^2}{4}}$$ Equality holds if and only if G is either a regular graph or a bi-degreed graph in which each vertex is of degree either δ or $n-1.$

For further information about the inequality in this theorem, we refer the reader to [42], where it is stated that equality can also occur if G is disconnected. However, in this paper we consider only the connected case and so give equality only for those graphs.

Theorem 2.3

([12, 27]). Let G and H be graphs with Laplacian spectra ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_n$ and ${\mu }_1\ge {\mu }_2\ge \dots \ge {\mu }_m$, respectively. Then the Laplacian spectrum of $\overline{G}$ is $n-{\lambda }_1,n-{\lambda }_2,\dots ,n-{\lambda }_{n-1},0$ and that of $G\nabla H$ is $n+m,n+{\mu }_1,n+{\mu }_2,\dots ,n+{\mu }_{m-1},0.$

Theorem 2.4

([12, 27]). If G is a graph of order n, then n is a Laplacian eigenvalue of G if and only if G is the join of two graphs.

Theorem 2.5

([24]). For a graph G, the following statements are equivalent$:$

1. G is d-regular.

2. $\rho (G)=d_G$, the average vertex degree.

3. $v={(1,1,\dots ,1)}^T$ is an eigenvector for $\rho (G).$

Proposition 2.1

([12, 20]). If j is a vertex of graph G, then $P_{G-j}(y)=P_G(y){\sum }_{i=1}^k\frac{{\alpha }_{ij}^2}{y-{\mu }_i}$, where k and α_ij are the number of distinct eigenvalues and the main angles (see [33]) of graph G, respectively.

Proposition 2.2

([39]). If G is a disconnected graph determined by the Laplacian spectrum, then so is the cone over G;, of the graph $K_1\nabla G$

Theorem 2.6

([12, 37]). If G is a non-regular graph with three distinct eigenvalues ${\theta }_0>{\theta }_1>{\theta }_2$, then the following hold$:$

1. G has diameter2.

2. If ${\theta }_0$ is not an integer, then G is a complete bipartite graph.

3. ${\theta }_1\ge 0$ with equality if and only if G is complete bipartite.

4. ${\theta }_2\le -\sqrt{2}$ with equality if and only if G is the path of length2.

Theorem 2.7

([41]). A graph has exactly one positive eigenvalue if and only if its vertices of positive degree form a complete multipartite graph.

In what follows, we always assume that w, r and $s\ge 3$ are natural numbers. In addition, when ${\text{Spec}}_A(G)={\text{Spec}}_A(K_w\nabla r{C}_s),$ we always assume that G is connected since some classes of disconnected graphs are not DAS. Some examples are the following:

${\text{Spec}}_A((2C_4\nabla (3C_4\cup K_3))\cup 5C_4)={\text{Spec}}_A(K_3\nabla 10C_4)$ but $(2C_4\nabla (3C_4\cup K_3))\cup 5C_4\ncong K_3\nabla 10C_4.$

${\text{Spec}}_A((C_5\nabla (6C_5\cup K_3))\cup 4C_5)={\text{Spec}}_A(K_3\nabla 11C_5)$ but $C_5\nabla (6C_5\cup K_3))\cup 4C_5\ncong K_3\nabla 11C_5.$

${\text{Spec}}_A((C_6\nabla (2C_6\cup K_3))\cup 2C_6)={\text{Spec}}_A(K_3\nabla 5C_6)$ but $C_6\nabla (2C_6\cup K_3))\cup 2C_6\ncong K_3\nabla 5C_6.$

However, if a graph cospectral with the multicone graph $K_3\nabla r{C}_s$ is connected, then it is DAS (see Theorem 3.1).

3. Main results

The aim of this section is to show that any graph cospectral with the multicone graph $K_w\nabla r{C}_s$ is either regular or bi-degreed.

Proposition 3.1.

Let G be a graph cospectral with the multicone graph $K_w\nabla r{C}_s$, and let $p=w+1$ and $q=2(w-1)-\mathit{rsw}$. Then ${\text{Spec}}_A(G)$ is: $$\underset{k=1}{\overset{\frac{s}{2}-1}{\cup }}\{{[-1]}^{w-1},{[2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{\left[2\right]}^{r-1},{[-2]}^r,{\left[\right(p-\sqrt{p^2-4q})/2]}^1,{\left[\right(p+\sqrt{p^2-4q})/2]}^1\}$$ if s is even, and $$\underset{k=1}{\overset{\frac{s-1}{2}}{\cup }}\{{[-1]}^{w-1},{[2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{\left[2\right]}^{r-1},{\left[\right(p-\sqrt{p^2-4q})/2]}^1,{\left[\right(p+\sqrt{p^2-4q})/2]}^1\}$$ if s is odd.

Proof.

It is well-known that the s-cycle C_s has eigenvalues $2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s},$ where $k=0,1,\dots ,s-1.$ All multiplicities are 2, except that of 2 and possibly –2. Now, by Theorem 2.1, the proof is straightforward. □

Lemma 3.1.

If G is a connected graph and ${\text{Spec}}_A(G)={\text{Spec}}_A(K_w\nabla r{C}_s)$, then $\delta (G)=w+2.$

Proof.

Let $x=\delta (G)-(w+2).$ First, it is clear that in this case equality holds in Theorem 2.2 if and only if x = 0. We claim that x = 0. To the contrary, we suppose that $x\ne 0.$ From Theorem 2.2 and Proposition 3.1 it follows that $$\begin{array}{c}\rho (G)=\frac{w+1+\sqrt{8m-4n(w+2)+{(w+3)}^2}}{2}\\ <\frac{w+1+x+\sqrt{8m-4n(w+2)+{(w+3)}^2+x^2+(2w+6-4n)x}}{2},\end{array}$$ where (as usual) n and m denote the numbers of vertices and edges in G.

For convenience, we let $B=8m-4n(w+2)+{(w+3)}^2\ge 0$ and $C=w+3-2n<0,$ and also let $q(x)=x^2+(2w+6-4n)x=x^2+2Cx.$ By replacing the new notations we have $\frac{w+1+\sqrt{B}}{2}<\frac{w+1+x+\sqrt{B+q(x)}}{2}$ or $\sqrt{B}<x+\sqrt{B+q(x)}.$ Then clearly $\sqrt{B}-\sqrt{B+q(x)}<x.$

We consider two cases:

Case 1:

x < 0. In this case, for any non-complete graph G we always have $\delta (G)<w+2$ (1). It is easy and straightforward to see that $|\sqrt{B}-\sqrt{B+q(x)}|>\left|x\right|,$ since $x<0.$ Transposing and squaring yields $2B+q(x)-2\sqrt{B(B+q(x))}>x^2.$ Replacing q(x) by $x^2+2Cx,$ we get $B+Cx>\sqrt{B(B+x^2+2Cx)}.$ Obviously $Cx\ge 0.$ By squaring the last inequality we get ${(B+Cx)}^2>{(\sqrt{B(B+x^2+2Cx)})}^2$ or $B^2+C^2{x}^2+2BCx>B^2+B{x}^2+2BCx$ or $C^2>B.$ Therefore, ${(w+3-2n)}^2=C^2>8m-4n(w+2)+{(w+3)}^2=B$ or ${(w+3)}^2-4n(w+3)+4n^2>8m-4n(w+2)+{(w+3)}^2.$ By simplifying this inequality we get $-4n+4n^2>8m$ or $m<\frac{n(n-1)}{2}.$

So, if $x<0,$ then G cannot be a complete graph (2). Combining (1) and (2) we get: $\delta (G)<w+2$ if and only if G is not a complete graph. To put that another way, G is a complete graph if and only if $\delta (G)>w+2,$ which is a contradiction, since if G is a complete graph, then $\delta (G)=w+2.$

Case 2:

$x>0.$

In the same way as Case 1, we can conclude that if G is complete, then $\delta (G)<w+2,$ a contradiction. So we must have x = 0. Therefore, the claim holds. □

Lemma 3.2.

If G is a connected graph and ${\text{Spec}}_A(G)={\text{Spec}}_A(K_w\nabla r{C}_s)$. Then G is either regular or bi-degreed with degrees $w-1+rs$ and w + 2.

Proof.

This follows from Lemma 3.1 together with Theorem 2.2. □

3.1. Graphs cospectral with the multicone graphs $K_1\nabla r{C}_s$

In this section, we show that any graph cospectral with the multicone graph $K_1\nabla r{C}_s$ is DAS.

Lemma 3.3.

If G is a connected graph and ${\text{Spec}}_A(G)={\text{Spec}}_A(K_w\nabla r{C}_s)$, then G is DAS.

Proof.

If r = 1 and s = 3 there is nothing to prove, since in this case G is regular (see Theorem 2.5). Hence we assume that $r>1$ or $s>3.$ By Lemma 3.2, it is clear that G has one vertex of degree rs, say v_j. We consider two cases:

Case 1:

s is even. From Proposition 2.1, it follows that $$P_{G-v_j}(x)={(x-{\mu }_0)}^{r-2}\prod _{i=1}^{\frac{s}{2}-1}{(x-{\mu }_i)}^{2r-1}{(x-{\mu }_{\frac{s}{2}})}^{r-1}\sum _{i=0}^{\frac{s}{2}+2}{\alpha }_{ij}^2{A}_i,$$ where $A_i={\prod }_{h\ne ih=0}^{\frac{s}{2}+2}(x-{\mu }_h),{\mu }_{\frac{s}{2}}=-2,{\mu }_{\frac{s}{2}+1}=1+\sqrt{1+rs},{\mu }_{\frac{s}{2}+2}=1-\sqrt{1+rs}$ and ${\mu }_i=2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2\pi i}{s}(0\le i\le \frac{s}{2}-1$).

Case 2:

s is odd. As in Case 1 from Proposition 2.1, it follows that $$P_{G-v_j}(x)={(x-{\mu }_0)}^{r-2}\prod _{i=1}^{\frac{s-1}{2}}{(x-{\mu }_i)}^{2r-1}\sum _{i=0}^{\frac{s-1}{2}+2}{\alpha }_{ij}^2{B}_l,$$ where $B_l={\prod }_{h\ne lh=0}^{\frac{s-1}{2}+2}(x-{\mu }_h),{\mu }_{\frac{s-1}{2}+1}=1+\sqrt{1+rs},{\mu }_{\frac{s-1}{2}+2}=1-\sqrt{1+rs}$ and ${\mu }_i=2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2\pi i}{r}(0\le i\le \frac{s-1}{2}$).

Now, from Lemma 3.2, it follows that $G-v_j$ is a 2-regular graph of order s. Therefore, we conclude that ${\text{Spec}}_A(G-v_j)$ is either ${\cup }_{k=1}^{\frac{s}{2}-1}\left\{{[2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{[2]}^r,{[-2]}^r\right\}$ or ${\cup }_{k=1}^{\frac{s-1}{2}}\left\{{[2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{[2]}^r\right\}.$ Hence $G-v_j\cong r{C}_s.$ So, $G\cong K_1\nabla r{C}_s,$ which completes the proof. □

Up to now, we have shown that the multicone graph $K_1\nabla r{C}_s$ is DAS. A natural question is what happens for multicone graph $K_w\nabla r{C}_s$ when w > 1. We answer this question in the following theorem.

Theorem 3.1.

Any connected graph cospectral with the multicone graph $K_w\nabla r{C}_s$ is DAS.

Proof.

We induct on w. By Lemma 3.3, the statement is true for w = 1. Assume that it is true for w, that is, if ${\text{Spec}}_A(G)={\text{Spec}}_A(K_w\nabla r{C}_s),$ then $G\cong K_w\nabla r{C}_s.$ We show that the claim is true for w + 1. We show that ${\text{Spec}}_A(H)={\text{Spec}}_A(K_{w+1}\nabla r{C}_s)$ implies that $H\cong K_{w+1}\nabla r{C}_s.$ Obviously, H has one vertex and w + rs edges more than H. By Lemma 3.2, G has w vertices of degree $w-1+rs$ and rs vertices of degree w + 2. On the other hand, H has w + 1 vertices of degree w + rs and rs vertices of degree $w+3.$ So, we must have $H\cong K_1\nabla G.$ Hence, the induction completes the proof. □

In the following, we present an alternative proof of Theorem 3.1.

Proof.

Let G be a graph cospectral with a multicone graph $K_w\nabla r{C}_s.$ By Lemma 3.2, G has a subgraph F that is regular of degree $w-1+rs.$ In other words, $G\cong K_w\nabla H,$ where H is a subgraph of G. Now, we remove the vertices of the complete graph K_w and we consider other rs vertices. Consider the subgraph H induced by these rs vertices. By Lemma 3.2 it must be regular of degree 2 and the multiplicity of 2 is r. In other words, H is a cycle or it is a disjoint union of several s-cycles. By Theorem 2.1, ${\text{Spec}}_A(H)$ is either ${\cup }_{k=1}^{\frac{s}{2}-1}\left\{{[2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{[2]}^r,{[-2]}^r\right\}$ or ${\cup }_{k=1}^{\frac{s-1}{2}}\left\{{[2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{[2]}^r\right\}.$ Hence ${\text{Spec}}_A(H)={\text{Spec}}_A(r{C}_s),$ and the result follows. □

3.2. Some classes of graphs $\overline{K_w\nabla r{C}_s}$ and their adjacency spectra

In this section, we show that the complements of the multicone graphs $K_w\nabla r{C}_3$ are DAS.

Theorem 3.2.

If G is a graph with ${\text{Spec}}_A(G)={\text{Spec}}_A(\overline{K_w\nabla r{C}_3})$, then $G\cong \overline{K_w\nabla r{C}_3}.$

Proof.

Assume that ${\text{Spec}}_A(G)=\{{[-3]}^{r-1},{[0]}^{2r+w},{[3r-3]}^1\}.$ If r = 1, there is nothing to prove. If r = 2, then Theorem 2.7 implies that $G\cong G_1+\overline{K_c},$ where G₁ is a complete multipartite graph and c is a natural number. On the other hand, it follows from Theorem 2.6 that G₁ is a complete bipartite graph. Therefore, $G_1\cong K_{3,3}.$ Hence $G\cong \overline{K_w}\cup K_{3,3}.$ Therefore, we can suppose that $r\ge 3.$ We know that regularity and the number of triangles of graph G can be determined by its adjacency spectrum. So, G is not regular graph and is not complete bipartite. Therefore, from Theorems 2.6 and 2.7 we conclude that G is disconnected and $G=G_1+\overline{K_d},$ where d is a natural number. Also, it is clear that G₁ has exactly three distinct eigenvalues. Now, for the sake of contradiction, we suppose that G₁ is not regular. From Theorem 2.6 it follows that G₁ is a complete bipartite graph and so G is itself bipartite, and this is a contradiction. Hence G₁ is regular and so $\rho (G_1)=3r-3.$ Now, from Theorem 2.7, it follows that G₁ is a multipartite graph and so must be congruent to the r-partite graph $K_{r(3)}=\overline{r{K}_3}$ with each partite set having three vertices. Therefore $G=G_1+\overline{K_w}\cong K_{r(3)}+\overline{K_w}\cong \overline{K_w\nabla r{K}_3},$ which proves the result. □

4. Laplacian spectral determinations of multicone graphs $K_w\nabla r{C}_s$

In this section, we show that with a few exceptions for small values of w, r and s ($w,r\ne 1$ and $s\ne 6,$ see [43], Figure 1), then the multicone graphs $K_w\nabla r{C}_s$ are DLS.

Figure 1. Wheel graph $W_{13}=K_1▽C_{12}.$

Theorem 4.1.

The multicone graphs $K_w\nabla r{C}_s$ are DLS, if $w,r\ne 1$ and $s\ne 6.$

Proof.

It is well-known that ${\text{Spec}}_L(C_s)=2-2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s},$ where $k=0,1,\dots ,s-1.$ All multiplicities are 2, except that of 0 and possibly 4. We use induction on $w.$ First, we assume that s is even. If w = 1, then the result is easily seen to hold by Proposition 2.2. Assume that it is true for w, that is, $${\text{Spec}}_L(G)={\text{Spec}}_L(K_w\nabla r{C}_s)=\underset{k=1}{\overset{\frac{s}{2}-1}{\cup }}\left\{{[w+rs]}^w,{[w+2-2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{\left[w\right]}^{r-1},{[w+4]}^r,{\left[0\right]}^1\right\}.$$ implies that $G\cong K_w\nabla r{C}_s.$ We show that the claim is true for w + 1, that is, we show that $${\text{Spec}}_L(H)={\text{Spec}}_L(K_{w+1}\nabla r{C}_s)=\underset{k=1}{\overset{\frac{s}{2}-1}{\cup }}\{{[w+1+rs]}^{w+1},{[w+3-2\hspace{0.17em}\text{cos}\hspace{0.17em}\frac{2k\pi }{s}]}^{2r},{[w+1]}^{r-1},{[w+5]}^r,{\left[0\right]}^1\}.$$ implies that $H\cong K_{w+1}\nabla r{C}_s.$ It is clear that H has one vertex and w + rs edges more than G. On the other hand, from Theorem 2.4, it follows that both of the graphs G and H are the join of two graphs. Furthermore, from Theorem 2.3, it follows that ${\text{Spec}}_L(K_1\nabla G)={\text{Spec}}_L(H).$ Therefore, we must have $H\cong K_1\nabla G.$ Hence, the result follows by the induction hypothesis.

The argument for s odd is similar, so we omit the details. □

4.1. Another property of multicone graphs $K_w\nabla r{C}_s$

A graph G is called perfect if its chromatic number $\chi (G)$ is equal to the order of its largest complete subgraph $\omega (G).$ The perfect graph theorem states that a graph G is perfect if and only if it contains no odd hole or antihole, where an odd hole is an induced odd cycle, C_n for $n\ge 5,$ and an odd antihole is the complement of an odd hole as an induced subgraph. Lovász proved that a graph is perfect if and only if its complement is perfect (see [18]). Here, we show that some graphs that are adjacency or Laplacian cospectral with $K_w\nabla r{C}_s$ must be perfect.

Theorem 4.2.

A connected graph G that is adjacency cospectral with the multicone graph $K_w\nabla r{C}_s$ is perfect and so is its complement $\overline{G}$ if and only if s = 3 or s is even.

Proof.

$(\Rightarrow )$: This follows at once since if s is odd, then clearly G has an odd hole.

$(\Leftarrow )$ It is easy to see that G cannot have an odd hole. Suppose that it has an odd antihole, that is, it contains $\overline{C_k}$ as an induced subgraph where k is odd and at least 5. Hence $\overline{G}=\overline{K_w}+\overline{r{C}_s}$ must contain C_k as an induced subgraph. It is easy to see that this cycle must be contained in $\overline{r{C}_s},$ which is the join $\overline{C_s}\nabla \overline{C_s}\nabla \dots \nabla \overline{C_s}$ of the complements of r cycles C_s, and this is clearly impossible. □

Theorem 4.3.

A graph G that is Laplacian cospectral with the multicone graph $K_w\nabla r{C}_s$ is perfect $($and so is its complement $\overline{G})$ if and only if s = 3 or s is even.

Proof.

The proof is analogous to that of Theorem 4.2 and so the details are omitted. □

5. Two conjectures

In this paper, it was proved that multicone graphs $K_w\nabla r{C}_s$ are both DAS (as connected graphs) and DLS ($w,r\ne 1$ and $s\ne 6$). We also show that the multicone complements $\overline{K_w\nabla r{C}_3}$ are DAS, and from [11] (Theorem 5.2) it follows that so are the graphs $\overline{K_w\nabla C_4}.$ We believe that these results can be extended and make the following conjectures:

Conjecture 1. The multicone complement graphs $\overline{K_w\nabla r{C}_s}$ are DAS.

Conjecture 2. The multicone graphs $K_w\nabla r{C}_s$ are DQS.

Disclosure statement

No potential conflict of interest was reported by the author(s).