On the spectral determinations of the connected multicone graphs

Abstract

In this study we investigate the spectra of the family of connected multicone graphs. A multicone graph is defined to be the join of a clique and a regular graph. Let $r$, $t$ and $s$ be natural numbers, and let $K_r$ denote a complete graph on $r$ vertices. It is proved that connected multicone graphs $K_r▽s{K}_t$, a natural generalization of friendship graphs, are determined by their adjacency spectra as well as their Laplacian spectra. Also, we show that the complement of multicone graphs $K_r▽s{K}_t$ is determined by their adjacency spectra, where $s\ne 2$.

Keywords:

• DS graph
• Friendship graph
• Multicone graph
• Adjacency spectrum
• Laplacian spectrum

1 Introduction

A long-standing question connecting graph theory and linear algebra has to do with the set of eigenvalues of the adjacency matrix of a graph, called the spectrum of the graph. Although it is well known that different graphs can have the same spectrum, it remains an open question as to whether most graphs have a spectrum shared by another graph or not. In fact, not many families of graphs are known that have their own spectrum, not shared by any other graphs. In the past decades, graphs that are determined by their spectrum have received much more and 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. We begin with some of the notation and terminology that will be used in the paper. All graphs considered here are simple and undirected, and, in general, given a graph $G$, $n$ will denote the number of vertices (also called its order) and $m$ the number of edges. If its vertices are $v_1,v_2,\dots ,v_n$, then its adjacency matrix $\mathbf{A}\left(G\right)$ is the $n\times n$ matrix with $a_{ij}=1$ if $v_i$ and $v_j$ are adjacent and $0$ otherwise. Its degree matrix is defined to be the diagonal matrix $\mathbf{D}\left(G\right)=\mathrm{diag}(d_1,d_2,\dots ,d_n)$, where $d_i$ is the degree of vertex $v_i$. Two other matrices are defined in terms of these: the Laplacian matrix is $\mathbf{L}\left(G\right)=\mathbf{D}\left(G\right)-\mathbf{A}\left(G\right)$ and the signless Laplacian matrix is $\mathbf{S}\left(G\right)=\mathbf{D}\left(G\right)+\mathbf{A}\left(G\right)$. We denote the characteristic polynomial $det(x\mathbf{I}-\mathbf{A})$ of $G$ by $P_G\left(x\right)$. A number $\lambda$ is an eigenvalue of $G$ if it is a root of this polynomial. Since $\mathbf{A}\left(G\right)$ is a symmetric matrix, all of its eigenvalues are real. The adjacency spectrum (Laplacian spectrum) of $G$, denoted ${Spec}_A\left(G\right)$ (${Spec}_L\left(G\right)$) , is the multiset of these eigenvalues. Two graphs $G$ and $H$ are said to be $A$-cospectral ( $L$-cospectral) if the corresponding adjacency spectra (Laplacian spectra) are the same. A graph $G$ is said to be $DAS$ ( $DLS$) if there is no other non-isomorphic graph $A$-cospectral ($L$-cospectral) with it, i.e., ${Spec}_A\left(H\right)={Spec}_A\left(G\right)$ (${Spec}_L\left(H\right)={Spec}_L\left(G\right)$) implies $G\cong H$. By analogy, we define determined by signless Laplacian spectrum ( $DQS$ for short) graphs. The key question that we consider is the extent to which the spectrum (of either type) of a graph is unique; that is, whether there is only one graph with that spectrum.

So far numerous examples of cospectral but non-isomorphic graphs have been constructed by interesting techniques such as Seidel switching, Godsil–McKay switching, Sunada or Schwenk method. For more information, one may see [1–3] and the references cited in them. Only a few graphs with very special structures have been reported to be determined by their spectra (DS, for short) (see [4–11] and the references cited in them). Recently Wei Wang and Cheng-Xian Xu have developed a new method in [10] to show that many graphs are determined by their spectrum and the spectrum of their complement.

One of the first investigations into this question was made in 1971 by Harary, et al. [12]. They asserted that (stated in slightly different terminology), based on the data they computed for graphs with up to seven vertices, “one is tempted to conjecture” that the fraction of graphs with spectra that are not unique decreases as the order increases. Technically, this is not exactly the same as the conjecture that the probability goes to $0$, but the two are closely related:

Unique Spectrum Conjecture

Almost all graphs are determined by their spectrum.

One fact that makes this conjecture especially intriguing is that there is one very interesting family of graphs for which the corresponding statement is known not to hold. In fact, Schwenk [13] proved that it is about as far off as it could be.

Co-spectral Tree Theorem

Almost no trees are determined by their spectrum.

What this means is that, as $n\to \infty$, the fraction of trees of order $n$ that have the same spectrum as another tree approaches $1$.

There are of course many versions of a conjecture such as the one above, not only for the different types of spectra, but also for different families of graphs.

The general terminology that we use may be found in standard textbooks on graph theory, but we give some that will be used here, some of which varies from author to author. In particular, we use the following notation on graph operations. We define the sum $G+H$ of two vertex-disjoint graphs $G$ and $H$ to be their union; that is, $V(G+H)=V\left(G\right)\cup V\left(H\right)$ and $E(G+H)=E\left(G\right)\cup E\left(H\right)$. Clearly, this can be extended to more graphs, $G_1+G_2+\cdots +G_k$, and the sum of $k$ copies of the same graph $G$ is denoted $kG$. The join $G▿H$ (or $G\ast H$) is obtained from $G+H$ by adding an edge from each vertex of $G$ to each vertex of $H$, that is, by adding the set of edges $\{vw:v\in V\left(G\right),w\in V\left(H\right)\}$.

The graphs that we consider here are combinations of sums and joins. We begin with a special case known as a friendship graph (also known as a (Dutch) windmill). Erdös, Rényi, and Sós [14] proved that if $G$ is the graph of $n$ people for which each pair has exactly one friend in common, then $G$ consists of $t$ triangles (with $n$ odd and $t=\frac{1}{2}(n-1)$), all having one common vertex. This graph is denoted $F_t$, and $F_2$, $F_3$, and $F_4$ are shown in Fig. 1.

Fig. 1 Three friendship graphs.

As a generalization of this, a multicone graph is the join of a complete graph and multiple copies of a regular graph $H$: $K_r▿sH$. Usually the graph $H$ is taken to be another complete graph, and the only multicone graphs that we consider in this paper are those of the form $K_r▿s{K}_t$. The friendship graph $F_s$ is thus the multicone $K_1▿s{K}_2$; another example of a multicone is shown in Fig. 2.

Fig. 2 A multicone graph.

It was conjectured (see Wang, et al. [11,15]) that friendship graphs are $DAS$. Recently, Cioabä, Haemers, Vermette, and Wang [5] proved the conjecture for $s\ne 16$; that is, if $G$ is adjacency $A$-cospectral with $F_s$ ($s\ne 16$), then $G\cong F_s$. For further information about some multicone graphs which have been characterized so far see [16–25].

This paper is organized as follows. In Section 2, we review some basic information and preliminaries. Then in Section 3, we state some algebraic properties about multicone graphs of the form $K_r▿s{K}_t$, while in Section 3.1, we show that these graphs are determined by their adjacency spectrum. In Section 4, we prove that their complements are also $DAS$, and in Section 5, we prove that these graphs are also determined by their Laplacian spectrum. Finally, in Section 6, we summarize our results and propose one conjecture for further research.

2 Preliminary results

In this section, we give some results from the literature that play important roles in the rest of the paper.

From both the adjacency spectrum and the Laplacian spectrum of a graph, one can deduce the number of vertices and the number of edges. The two spectra also give additional information [26–29]. We defer a similar result for the Laplacian spectrum to Section 5, where that spectrum determination is developed.

Theorem 2.1

Given a graph $G$, the following can be deduced from its adjacency spectrum:

(a) the number of closed walks of each length;

(b) whether or not $G$ is bipartite;

(c) whether or not $G$ is regular, and if so, the degree of regularity.

The next several results concern degrees and eigenvalues in graphs. Recall that $\Delta \left(G\right)$ (sometimes just $\Delta$) denotes the maximum degree of a vertex of a graph $G$, and similarly $\delta \left(G\right)$ (or just $\delta$) denotes the minimum degree. If the two are different and they are the only degrees in $G$ and $\delta \left(G\right)$ is positive, then $G$ is said to be bi-regular or bi-degreed. Also, the largest eigenvalue of $G$ is called the spectral radius (sometimes called the spectral index) and is denoted $\rho \left(G\right)$ (or just $\rho$).

The following result, [15–19,30] gives a bound on the spectral radius. For further information about this inequality we refer the reader to [15] (see the first paragraph after Corollary 2.2 and also Theorem 2.1 of [15]).

Theorem 2.2

If $G$ is a graph with $n$ vertices, $m$ edges, minimum degree $\delta$, and spectral radius $\rho$, then $$\rho \le \frac{\delta -1}{2}+\sqrt{2m-n\delta +\frac{{(\delta +1)}^2}{4}}.$$Equality holds if and only if $G$ is either regular or is bi-regular with $\Delta =n-1$.

The next theorem gives a characterization of some graphs with three distinct eigenvalues [16,31].

Theorem 2.3

[31] A graph has exactly one positive eigenvalue if and only if it is a complete multipartite graph with possibly some isolated vertices.

The next two theorems concern regular graphs; the first can be found in Knauer [32] and the second in Bapat [33].

Theorem 2.4

Let $G$ be a graph with spectral radius $\rho$. Then the following statements are equivalent:

(1) $G$ is regular.

(2) $\rho$ is the average vertex degree in $G$.

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

Theorem 2.5

If $G$ is an $r$-regular graph with eigenvalues ${\lambda }_1(=r),{\lambda }_2,\dots ,{\lambda }_n$, then $n-1-{\lambda }_1,-1-{\lambda }_2,\dots ,-1-{\lambda }_n$ are the eigenvalues of the complement $\overline{G}$ of $G$.

We turn now to a theorem on graphs that are not regular.

Theorem 2.6

[34,35] If $G$ is not regular and has exactly three eigenvalues ${\theta }_1>{\theta }_2>{\theta }_3$, then:

(a) $G$ has diameter $2$;

(b) if ${\theta }_1$ is not an integer, then $G$ is complete bipartite;

(c) ${\theta }_2\ge 0$ with equality if and only if $G$ is complete bipartite;

(d) ${\theta }_3<-2$.

The next theorem gives the characteristic polynomial of the join of two regular graphs in terms of their individual polynomials (see also [16–19,27]).

Theorem 2.7

[27] For $i=\text{1,2}$, let $G_i$ be an $r_i$-regular graph of order $n_i$. Then the characteristic polynomial of their join is $$P_{G_1▿G_2}\left(x\right)=P_{G_1}\left(x\right)P_{G_2}\left(x\right)(1-\frac{n_1{n}_2}{(x-r_1)(x-r_2)}).$$

The next several theorems are also on the characteristic polynomial of a graph; the first can be found in [16,32]).

Theorem 2.8

The following statements are equivalent for a nontrivial graph $G$ with characteristic polynomial $P_G\left(x\right)={\sum }_{i=0}^n{c}_i{x}^i$, spectrum ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$, and spectral radius $\rho$.

(1) $G$ is bipartite.

(2) The coefficients $c_i$ for $i$ odd are all $0$.

(3) For each $i$, ${\lambda }_{n+1-i}=-{\lambda }_i$.

(4) $\rho =-{\lambda }_n$.

We note that statement $\left(3\right)$ in this theorem implies that each eigenvalue has the same multiplicity as its negative.

The next result, including a discussion of main angles (For further information about main angles see [36]), may be found in [16–19,27]).

Theorem 2.9

If $j$ is a vertex of graph $G$, then $P_{G-j}\left(x\right)=P_G\left(x\right){\sum }_{i=1}^m\frac{{\alpha }_{ij}^2}{x-{\mu }_i}$, where $m$ and ${\alpha }_{ij}$ are the number of distinct eigenvalues and the main angle of graph $G$, respectively.

Proposition 2.1

[3] Let $G$ be a disconnected graph that is determined by the Laplacian spectrum. Then the cone over $G$, the graph $H$; that is, obtained from $G$ by adding one vertex that is adjacent to all vertices of $G$, is also determined by its Laplacian spectrum.

3 Connected graphs $A$-cospectral with a multicone graph $K_r▽s{K}_t$

In this section, we give some results on graphs that are cospectral with a multicone graph $K_r▿s{K}_t$. Note that the order of $K_r▿s{K}_t$ is $r+st$, which we denote by $n$. In giving the spectrum of a graph, we often use the common notation of ${\left[c\right]}^k$ for an eigenvalue $c$ of multiplicity $k\ge 1$.

Proposition 3.1

If $G$ is a graph $A$-cospectral with multicone graph $K_r▿s{K}_t$, then $${Spec}_A\left(G\right)=\left\{{[-1]}^{r-1+s(t-1)},{[t-1]}^{s-1},{\left[\frac{a+\sqrt{a^2-4b}}{2}\right]}^1,{\left[\frac{a-\sqrt{a^2-4b}}{2}\right]}^1\right\},$$where $a=r+t-2$ and $b=(r-1)(t-1)-rst.$

Proof

We know that ${Spec}_A\left(K_t\right)=\{{[-1]}^{t-1},{[t-1]}^1\}$ (see [33]). Now, by Theorem 2.7 the proof is clear. □

3.1 Adjacency spectrum determination of the connected multicone graphs $K_r▿s{K}_t$

The aim of this section is to show that multicone graphs $K_r▿s{K}_t$ are $DAS$.

Lemma 3.1

If $G$ is a connected graph $A$-cospectral with a multicone graph $K_r▿s{K}_t$, then $\delta \left(G\right)=r+t-1$.

Proof

Let $x=\delta \left(G\right)-(r+t-1)$. It follows from Theorem 2.4 that:

$G$ is a regular graph if and only if $s=1$ if and only if $G$ is a complete graph.

Consider the following two cases:

Case 1. $s=1$. In this case $\delta \left(G\right)=r+t-1$ and there is nothing to prove.

Case 2. $s\ge 2$ ($s\ne 1$). We show that $x=0$.

Suppose not and so $x\ne 0$ (in this case $\delta \left(G\right)\ne r+t-1$). It follows from Theorem 2.2 and Proposition 3.1 that $$\rho \left(G\right)=\frac{r+t-2+\sqrt{8m-4n(r+t-1)+{(r+t)}^2}}{2}<\frac{r+t-2+x+\sqrt{8m-4n(r+t-1)+{(r+t)}^2+x^2+(2r+2t-4n)x}}{2},$$where (as usual) $n$ and $m$ denote the numbers of vertices and edges in $G$, respectively.

For convenience, we let $B=8m-4n(r+t-1)+{(r+t)}^2$ and $C=r+t-2n$, and also let $g\left(x\right)=x^2+2(r+t-2n)x=x^2+2Cx.$

Then clearly (1) $$\sqrt{B}-\sqrt{B+g\left(x\right)}<x.$$(1)

We consider the following two subcases (we show that none of the following two subcases can happen):

Subcase 2.1. $x<0$.

Then $$|\sqrt{B}-\sqrt{B+g\left(x\right)}|>\left|x\right|,\text{since}x<0.$$Transposing and squaring yields $$2B+g\left(x\right)-2\sqrt{B(B+g\left(x\right))}>x^2.$$Replacing $g\left(x\right)$ by $x^2+2Cx$, we get (2) $$B+Cx>\sqrt{B(B+x^2+2Cx)}.$$(2) Obviously $Cx>0$, since $C=r+t-2n=r+t-2(r+st)=-r+t(1-2s)<0$ and $x<0$. Squaring again and simplifying yields (3) $$C^2>B.$$(3)

Therefore, (4) $$m<\frac{n(n-1)}{2}.$$(4)

Therefore, if $x<0$, then $G$ is not a complete graph. Or if $\delta \left(G\right)<r+t-1$, then $G$ is not a complete graph $\left(†\right)$. On the other hand, if $x<0$ for any non-complete graph $G$ we always have $\delta \left(G\right)<r+t-1$ $\left(‡\right)$. Combining $\left(†\right)$ and $\left(‡\right)$ we get: $\delta \left(G\right)<r+t-1$ if and only if $G$ is not a complete graph. To put that another way, $x>0$ if and only if $G$ is a complete graph, a contradiction, since if $G$ is a complete graph, then $x=0$.

Subcase 2.2. $x>0$. In this case if $G$ is non-complete graph, then $\delta \left(G\right)>r+t-1$ (*).

On the other hand by a similar argument of Subcase 2.1 for $x>0$, if $\delta \left(G\right)>r+t-1$, then $G$ is not a complete graph (**). Combining (*) and (**) we have: $x<0$ if and only if $G$ is a complete graph, a contradiction. So, we must have $x=0$. Therefore, the assertion holds. □

Lemma 3.2

If $G$ is a connected graph $A$-cospectral with a multicone graph $K_r▿s{K}_t$, then it is either regular or bi-degreed with degrees $\delta =r+t-1$ and $\Delta =r+st-1$.

Proof

The result follows from Lemma 3.1 and Theorem 2.2. □

In the following, we show that any connected graph $A$-cospectral with the multicone graph $K_1▿s{K}_t$ is $DAS$.

Lemma 3.3

If $G$ is a connected graph $A$-cospectral with the multicone graph $K_1▿s{K}_t$, then $G$ is $DAS$.

Proof

If $s=1$, there is nothing to prove, since graph $G$ in this case is a complete graph (see Theorem 2.4). Hence we suppose that $s\ne 1$. In this case, $G$ is bi-degreed (see Lemma 3.2). By Lemma 3.2 any vertex of $G$ is either of degree $1+t-1=t$ or $1+st-1=st$. Let $G$ has $\alpha$ vertices (vertex) of degree $st$. Therefore, by Theorem 2.1 (iii) (sum of vertices degree of $G$ that is sum of squares of the eigenvalues of $G$) and Proposition 3.1 we have: $$\left(\alpha \right)st+(st+1-\alpha )t=s(t-1)\left({(-1)}^2\right)+(s-1){(t-1)}^2+{\left(\frac{t-1+\sqrt{{(t-1)}^2+4st}}{2}\right)}^2+{\left(\frac{t-1-\sqrt{{(t-1)}^2+4st}}{2}\right)}^2=st+st\left(t\right)=st(t+1).$$By solving the equation we get $\alpha =1$. This means that $G$ has one vertex of degree $st$, say $j$ and $st$ vertices of degree $t$. It follows from Theorem 2.9 that $$P_{G-j}\left(x\right)={(x-{\mu }_3)}^{s(t-1)-1}{(x-{\mu }_4)}^{s-2}({\alpha }_{1j}^2{A}_1+{\alpha }_{2j}^2{A}_2+{\alpha }_{3j}^2{A}_3+{\alpha }_{4j}^2{A}_4),$$where $$A_1=(x-{\mu }_2)(x-{\mu }_3)(x-{\mu }_4),$$$$A_2=(x-{\mu }_1)(x-{\mu }_3)(x-{\mu }_4),$$$$A_3=(x-{\mu }_1)(x-{\mu }_2)(x-{\mu }_4),$$$$A_4=(x-{\mu }_1)(x-{\mu }_2)(x-{\mu }_3),$$with ${\mu }_1=\frac{t-1+\sqrt{{(t-1)}^2+4st}}{2}$, ${\mu }_2=\frac{t-1-\sqrt{{(t-1)}^2+4st}}{2}$, ${\mu }_3=-1$, and ${\mu }_4=t-1$.

As stated at the beginning of this lemma $G$ has one vertex of degree $st$ and $st$ vertices of degree $t$. This means that graph $G-j$ has $st$ vertices of degree $t-1$. In other words, $G-j$ is a $(t-1)$-regular graph and it has $st$ eigenvalues (vertices). It is clear that by removing the vertex $j$ the number of edges that are deleted from graph $G$ is $st=\left|V(G-j)\right|$. On the other hand, the number of the closed walks of length 2 belonging to $G$ is: $$s(t-1)\left({(-1)}^2\right)+(s-1){(t-1)}^2+{\left(\frac{t-1+\sqrt{{(t-1)}^2+4\left(st\right)}}{2}\right)}^2+{\left(\frac{t-1-\sqrt{{(t-1)}^2+4\left(st\right)}}{2}\right)}^2=st+st\left(t\right)=st(t+1).$$

This means that the number of the closed walks of length 2 belonging to $G-j$ is $st(t+1)-2\left|V(G-j)\right|=st(t+1)-2\left(st\right)=st(t-1)$. (Or one can say that since $G-j$ is a $(t-1)$-regular graph and it has $st$ eigenvalues, so the number of the closed walks of length 2 belonging to $G-j$ is $st(t-1)$).

Now, by computing the number of the closed walks of length 1 (sum of all eigenvalues that is equal to zero) and 2 belonging to $G-j$, we have: $$\gamma +\zeta +t-1=-[(s-2){\mu }_4+(s(t-1)-1){\mu }_3],$$ $${\gamma }^2+{\zeta }^2+{(t-1)}^2=st(t-1)-[(s-2){\mu }_4^2+(s(t-1)-1){\mu }_3^2],$$where $\gamma$ and $\zeta$ are the eigenvalues of $G-j$. The roots are $\gamma =t-1$ and $\zeta =-1$. Therefore, ${Spec}_A(G-j)=\{{\left[-1\right]}^{s(t-1)},{\left[t-1\right]}^s\}={Spec}_A\left(s{K}_t\right)$. Hence, $G-j\cong s{K}_t$, and so $G\cong K_1▿s{K}_t$. □

Until now, we have considered only graphs $A$-cospectral with the multicone graph $K_1▿s{K}_t$ (windmill-like graphs with larger sails). The next theorem extends our result to the general multicone graph $K_r▿s{K}_t$.

Theorem 3.1

If $G$ is a connected graph $A$-cospectral with a multicone graph $K_r▿s{K}_t$, then $G$ is $DAS$.

Proof

If $s=1$ the proof is clear. Take $s\ge 2$. We perform the mathematical induction on $r$. For $r=1$, the proof follows from Lemma 3.3. Let the claim be true for $r$; that is, if ${\mathrm{Spec}}_A\left(M\right)={\mathrm{Spec}}_A(K_r▽s{K}_t)$, then $M\cong K_r▽s{K}_t$, where $M$ is an arbitrary graph $A$-cospectral with a multicone graph $K_r▽s{K}_t$. We show that the claim is true for $r+1$; that is, we show that if ${\mathrm{Spec}}_A\left(G\right)={\mathrm{Spec}}_A(K_{r+1}▽s{K}_t)$, then $G\cong K_{r+1}▽s{K}_t$, where $G$ is a graph. It is clear that $G$ has one vertex and $r+st$ edges more than $M$. By a similar argument that stated at the beginning of Lemma 3.3 one may deduce that $M$ has $r$ vertices of degree $r+st-1$ and $st$ vertices of degree $r+t-1$ and also $G$ has $r+1$ vertices of degree $r+st$ and $st$ vertices of degree $r+t$. Hence we must have $G\cong K_1▽M$, since by Lemma 3.2 $G$ is bi-degreed and has $r+1$ vertices of degree $r+st$ and $st$ vertices of degree $r+t$. Now, the induction hypothesis completes the proof. □

It is well-known that the smallest non-isomorphic cospectral graphs are ${\Gamma }_1=C_4\cup K_1$ and ${\Gamma }_2=K_{1,4}$ (see Fig. 3). Note that ${\Gamma }_1=\overline{F_2}$ (the complement of the windmill $F_2$) is not a connected graph while ${\Gamma }_2$ is connected. Thus, we see that $\overline{F_2}$ is not $DAS$. However, Abdollahi, Janbaz and Oboudi [26] proved that if $n\ne 2$, then $\overline{F_n}=\overline{K_1▿n{K}_2}$ is $DAS$. A natural question is what happens with the complement of the general multicone graph $(K_r▿s{K}_t)$. We address this in the next section.

Fig. 3 A pair of $A$-cospectral graphs but non-isomorphic.

4 Graphs $A$-cospectral with complements of multicone graphs $K_r▿s{K}_t$

In this section we investigate the complements of the multicone graphs $K_r▿s{K}_t$. Clearly, if $s=1$, then the multicone graph is just the complete graph $K_{r+t}$, and so its complement is $(r+t)K_1$ with spectrum $\left\{{\left[0\right]}^{r+t}\right\}$. Clearly no other graph has this spectrum. On the other hand, the case $s=2$ is much more interesting. The complement of $K_r▿2K_t$ is the union $r{K}_1+K_{t,t}$. The adjacency spectrum is $\{[-t],\left[t\right],{\left[0\right]}^{2t+r-2}\}$. Our next theorem determines which graphs have this spectrum.

Theorem 4.1

Let $G$ be a graph with adjacency spectrum $\{[-t],\left[t\right],{\left[0\right]}^{2t+r-2}\}$.

$\mathrm{(a)}$ $G$ is not connected if and only if $G\cong \overline{(K_r▿2K_t)}$.

$\mathrm{(b)}$ If $G$ is connected if and only if $G\cong K_{p,q}$, where $p$ and $q$ are the two roots of the equation $x^2-(r+2t)x+t^2=0$.

Proof

(a) Assume that $G$ is disconnected. Then by Theorem 2.3, there is a complete multipartite graph $H$ for which $G\cong H+c{K}_1$, where $0\le c\le 2t+r-2$. We show that $c=r$. If $t⩾2$, then $H$ has precisely three different eigenvalues ($L$ has two distinct eigenvalues if and only if $L=d{K}_n$, where $d$ and $n$ are natural numbers. Also note that ${Spec}_A\left(K_n\right)=\left\{{\left[n-1\right]}^1,{\left[-1\right]}^{n-1}\right\}$). So by Theorem 2.8 $H$ is a bipartite graph. Hence $H\cong K_{t,t}$, and so $c=r$. Therefore, $G=\overline{K_r▿2K_t}$. If $t=1$, then $H\cong K_{1,1}=K_2$ and $c=r$. The converse is clear.

(b) Assume that $G$ is connected. Then $G$ cannot be regular, so by Theorem 2.6, it must be a complete bipartite graph $K_{p,q}$, for some $p$ and $q$. The spectrum of $K_{p,q}$ is known to be $\{{\left[\sqrt{pq}\right]}^1,{[-\sqrt{pq}]}^1,{\left[0\right]}^{p+q-2}\}$ (see, for example, [32]). This is also the spectrum of $G\cong \overline{K_r▿2K_t}$ when $p+q=2t+r$ and $pq=t^2$, that is, when $p$ (and likewise $q$) satisfies $x^2-(r+2t)x+t^2=0$. The converse is straightforward. □

As a consequence of this theorem, we have the result that the complement of a multicone graph $\overline{K_r▿2K_t}$ is not $DAS$. However, these are the only graphs in this family that are not, as our next theorem shows. Before presenting the theorem, we note that $\overline{K_r▿s{K}_t}\cong r{K}_1+K_{s\left(t\right)}$, where $K_{s\left(t\right)}$ denotes the complete $s$-partite graph with each of the partite sets being of size $t$. We also note that the spectrum of this graph is $\{{[-t]}^{s-1},{\left[0\right]}^{s(t-1)+r},\left[t(s-1)\right]\}$.

Theorem 4.2

For $s\ge 3$, graphs $\overline{K_r▿s{K}_t}$ are $DAS$.

Proof

Let ${Spec}_A\left(G\right)=\{{[-t]}^{s-1},{\left[0\right]}^{s(t-1)+r},\left[t(s-1)\right]\}={Spec}_A\left(\overline{K_r▿s{K}_t}\right)$. It follows from Theorem 2.6 that if $G$ is connected, then it is a complete bipartite graph. Therefore, it follows from Theorem 2.8 that $s=2$, a contradiction. Hence $G$ is disconnected. Now, by Theorem 2.3 there is a complete multipartite graph $H$ for which $G\cong H+a{K}_1$, where $s(t-1)+r\ge a\ge 1$. We claim that $H$ must be regular. Suppose not and so, as before, by Theorem 2.6 $H$ must be a complete bipartite graph, and this is impossible. Thus, $H$ must have at least three partite sets, and since it is regular, it must be $K_s\left(t\right)$, and so $G\cong r{K}_1+K_{s\left(t\right)}$, establishing the result. □

5 Laplacian spectrum determination of multicone graphs $K_r▿s{K}_t$

In this section, we consider the Laplacian spectrum of multicones. Recall that the Laplacian matrix of a graph $G$ is the matrix $\mathbf{L}\left(G\right)=\mathbf{D}\left(G\right)-\mathbf{A}\left(G\right)$, where $\mathbf{A}\left(G\right)$ is the adjacency matrix of $G$ and $\mathbf{D}\left(G\right)$ is the degree matrix, and the Laplacian spectrum of $G$, denoted ${\mathrm{Spec}}_L\left(G\right)$, is the spectrum of $\mathbf{L}\left(G\right)$.

We begin with some general results of [16–19,37] on Laplacian spectra.

Theorem 5.1

Let $G$ and $H$ be graphs with Laplacian spectra ${\alpha }_1\ge {\alpha }_2\ge \cdots \ge {\alpha }_n$ and ${\beta }_1\ge {\beta }_2\ge \cdots \ge {\beta }_k$, respectively. Then

(a) the Laplacian spectrum of the complement $\overline{G}$ is $n-{\alpha }_1,n-{\alpha }_2,\dots ,n-{\alpha }_n-1,0$, and

(b) the Laplacian spectrum of the join $G▿H$ is $n+k,k+{\alpha }_1,k+{\alpha }_2,\dots ,k+{\alpha }_n-1,n+{\beta }_1,n+{\beta }_2,\dots ,n+{\beta }_{k-1},0$.

Theorem 5.2

The order $n$ of a graph $G$ is a Laplacian eigenvalue of $G$ if and only if $G$ is the join of two graphs.

The next result gives the Laplacian spectrum of multicone graphs $K_r▿s{K}_t$.

Proposition 5.1

The Laplacian spectrum of multicone $K_r▿s{K}_t$ is: $$\{{[r+st]}^r,{[r+t]}^{s(t-1)},{\left[r\right]}^{s-1},{\left[0\right]}^1\}.$$

Proof

It is clear that ${\mathrm{Spec}}_L\left(K_t\right)=\{{\left[t\right]}^{t-1},{\left[0\right]}^1\}$ and so ${\mathrm{Spec}}_L\left(s{K}_t\right)=\{{\left[t\right]}^{s(t-1)},{\left[0\right]}^s\}$. Now, By Theorem 5.1 (b) the proof is straightforward. □

Theorem 5.3

Multicone graphs $K_r▿s{K}_t$ are $DLS$.

Proof

If $s=1$, the proof is clear. So, we consider $s\ge 2$. The proof is by induction on $r$. By Proposition 2.1 the result is clearly true when $r=1$. Assume that the theorem holds for $r$; that is, if ${\mathrm{Spec}}_L\left(G\right)={\mathrm{Spec}}_L(K_r▿s{K}_t)=\{{[r+st]}^r,{[r+t]}^{s(t-1)},{\left[r\right]}^{s-1},{\left[0\right]}^1\}$, then $G\cong K_r▿s{K}_t.$ We show that if ${\mathrm{Spec}}_L\left(H\right)={\mathrm{Spec}}_L(K_{r+1}▿s{K}_t)=\{{[r+st+1]}^{r+1},{[r+t+1]}^{s(t-1)},{[r+1]}^{s-1},{\left[0\right]}^1\}$, then $H\cong K_{r+1}▿s{K}_t.$ It follows from Theorem 5.2 that $H$ and $G$ are the join of two graphs. On the other hand, $H$ has one vertex, say $e$ and $r+st$ edges more than $G$. By Theorem 5.1 (a) ${\mathrm{Spec}}_L\left(\overline{H}\right)=\{{\left[0\right]}^{r+2},{[st-t]}^{s(t-1)},{\left[st\right]}^{s-1}\}$ and ${\mathrm{Spec}}_L\left(\overline{G}\right)=\{{\left[0\right]}^{r+1},{[st-t]}^{s(t-1)},{\left[st\right]}^{s-1}\}$. We know that a graph is $DLS$ if and only if its complement is $DLS$. Obviously, ${\mathrm{Spec}}_L\left(\overline{H}\right)={\mathrm{Spec}}_L\left(\overline{G}\right)\cup {\mathrm{Spec}}_L\left(K_1\right)$. On the other hand, $\overline{H}$ has only one vertex more than $\overline{G}$. Therefore, $\overline{H}=\overline{G}\cup K_1$ or $H=G▽K_1$. Now, by the induction hypothesis the proof is completed. □

Since friendship graphs form a special family of multicone graphs, we have the following result.

Corollary 5.1

The friendship graph $F_s=K_1▿s{K}_2$ is $DLS$.

6 Conclusion remarks and a conjecture

The following theorem summarizes the most important results in this paper regarding the adjacency and Laplacian spectrum determination of multicone graphs.

Theorem 6.1

$\mathrm{(a)}$ For all $r,s,$ and $t$, the connected multicone graph $K_r▿s{K}_t$ is both $DAS$ and $DLS$.

$\mathrm{(b)}$ For all $r,s,$ and $t$ with $s>2$, the graphs $\overline{K_r▿s{K}_t}$ are both $DAS$ and $DLS$.

Of course, friendship graphs are an interesting, and in some ways exceptional, special type of multicone, consisting as they do, of a collection of triangles with one common vertex. Cioabä, et al. [5] proved that the friendship graph $F_{16}$ is not $DAS$, and, as we observed earlier, neither is the complement of $F_2$, and these are the only exceptions.

Remark 1

$\mathrm{(a)}$ For $s\ne 16$, the friendship graph $F_s=K_1▿s{K}_2$ is $DAS$ and for any $s$, $F_s$ is $DLS$.

$\mathrm{(b)}$ For $s\ne 2$, the friendship graph $\overline{F_s=K_1▿s{K}_2}$ is $DAS$ and for any $s$, $\overline{F_s}$ is $DLS$.

$\mathrm{(c)}$ Consider $K_{1,3}▽K_{r-1}=3K_1▽K_r$ and $(K_3\cup K_1)▽K_{r-1}$ that have the same signless Laplacian spectrum (see Corollary 2.2 of [38] and Theorem 2.1 of [38]) but are non-isomorphic.

As we noted at the beginning of the paper, a third type of matrix that gives the adjacencies of a graph has been studied, the signless Laplacian matrix, defined as $\mathbf{S}\left(G\right)=\mathbf{D}\left(G\right)+\mathbf{A}\left(G\right)$ (in contrast to the ordinary Laplacian $\mathbf{S}\left(G\right)=\mathbf{D}\left(G\right)-\mathbf{A}\left(G\right)$), with the corresponding determined by signless Laplacian spectrum. Friendship graphs are known to be $DQS$. Thus, we conclude with the following conjecture.

Conjecture 1

Multicone graphs $K_r▿s{K}_t$, except in multicone graphs $K_r▽3K_1$, are $DQS$.