![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
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 ,
and
be natural numbers, and let
denote a complete graph on
vertices. It is proved that connected multicone graphs
, 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
is determined by their adjacency spectra, where
.
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 ,
will denote the number of vertices (also called its order) and
the number of edges. If its vertices are
, then its adjacency matrix
is the
matrix with
if
and
are adjacent and
otherwise. Its degree matrix is defined to be the diagonal matrix
, where
is the degree of vertex
. Two other matrices are defined in terms of these: the Laplacian matrix is
and the signless Laplacian matrix is
. We denote the characteristic polynomial
of
by
. A number
is an eigenvalue of
if it is a root of this polynomial. Since
is a symmetric matrix, all of its eigenvalues are real. The adjacency spectrum (Laplacian spectrum) of
, denoted
(
) , is the multiset of these eigenvalues. Two graphs
and
are said to be
-cospectral (
-cospectral) if the corresponding adjacency spectra (Laplacian spectra) are the same. A graph
is said to be
(
) if there is no other non-isomorphic graph
-cospectral (
-cospectral) with it, i.e.,
(
) implies
. By analogy, we define determined by signless Laplacian spectrum (
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 [Citation1–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 [Citation4–11] and the references cited in them). Recently Wei Wang and Cheng-Xian Xu have developed a new method in [Citation10] 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. [Citation12]. 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 , 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 [Citation13] 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 , the fraction of trees of order
that have the same spectrum as another tree approaches
.
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 of two vertex-disjoint graphs
and
to be their union; that is,
and
. Clearly, this can be extended to more graphs,
, and the sum of
copies of the same graph
is denoted
. The join
(or
) is obtained from
by adding an edge from each vertex of
to each vertex of
, that is, by adding the set of edges
.
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 [Citation14] proved that if is the graph of
people for which each pair has exactly one friend in common, then
consists of
triangles (with
odd and
), all having one common vertex. This graph is denoted
, and
,
, and
are shown in .
As a generalization of this, a multicone graph is the join of a complete graph and multiple copies of a regular graph :
. Usually the graph
is taken to be another complete graph, and the only multicone graphs that we consider in this paper are those of the form
. The friendship graph
is thus the multicone
; another example of a multicone is shown in .
It was conjectured (see Wang, et al. [11,15]) that friendship graphs are . Recently, Cioabä, Haemers, Vermette, and Wang [Citation5] proved the conjecture for
; that is, if
is adjacency
-cospectral with
(
), then
. 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 , 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
, 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 , the following can be deduced from its adjacency spectrum:
(a) the number of closed walks of each length;
(b) whether or not is bipartite;
(c) whether or not is regular, and if so, the degree of regularity.
The next several results concern degrees and eigenvalues in graphs. Recall that (sometimes just
) denotes the maximum degree of a vertex of a graph
, and similarly
(or just
) denotes the minimum degree. If the two are different and they are the only degrees in
and
is positive, then
is said to be bi-regular or bi-degreed. Also, the largest eigenvalue of
is called the spectral radius (sometimes called the spectral index) and is denoted
(or just
).
The following result, [15–19,30] gives a bound on the spectral radius. For further information about this inequality we refer the reader to [Citation15] (see the first paragraph after Corollary 2.2 and also Theorem 2.1 of [Citation15]).
Theorem 2.2
If is a graph with
vertices,
edges, minimum degree
, and spectral radius
, then
Equality holds if and only if
is either regular or is bi-regular with
.
The next theorem gives a characterization of some graphs with three distinct eigenvalues [16,31].
Theorem 2.3
[Citation31] 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 [Citation32] and the second in Bapat [Citation33].
Theorem 2.4
Let be a graph with spectral radius
. Then the following statements are equivalent:
(1) is regular.
(2) is the average vertex degree in
.
(3) is an eigenvector for
.
Theorem 2.5
If is an
-regular graph with eigenvalues
, then
are the eigenvalues of the complement
of
.
We turn now to a theorem on graphs that are not regular.
Theorem 2.6
[34,35] If is not regular and has exactly three eigenvalues
, then:
(a) has diameter
;
(b) if is not an integer, then
is complete bipartite;
(c) with equality if and only if
is complete bipartite;
(d) .
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
[Citation27] For , let
be an
-regular graph of order
. Then the characteristic polynomial of their join is
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 with characteristic polynomial
, spectrum
, and spectral radius
.
(1) is bipartite.
(2) The coefficients for
odd are all
.
(3) For each ,
.
(4) .
We note that statement 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 [Citation36]), may be found in [16–19,27]).
Theorem 2.9
If is a vertex of graph
, then
, where
and
are the number of distinct eigenvalues and the main angle of graph
, respectively.
Proposition 2.1
[Citation3] Let be a disconnected graph that is determined by the Laplacian spectrum. Then the cone over
, the graph
; that is, obtained from
by adding one vertex that is adjacent to all vertices of
, is also determined by its Laplacian spectrum.
3 Connected graphs ![](//:0)
-cospectral with a multicone graph ![](//:0)
![](//:0)
In this section, we give some results on graphs that are cospectral with a multicone graph . Note that the order of
is
, which we denote by
. In giving the spectrum of a graph, we often use the common notation of
for an eigenvalue
of multiplicity
.
Proposition 3.1
If is a graph
-cospectral with multicone graph
, then
where
and
Proof
We know that (see [Citation33]). Now, by Theorem 2.7 the proof is clear. □
3.1 Adjacency spectrum determination of the connected multicone graphs ![](//:0)
![](//:0)
The aim of this section is to show that multicone graphs are
.
Lemma 3.1
If is a connected graph
-cospectral with a multicone graph
, then
.
Proof
Let . It follows from Theorem 2.4 that:
is a regular graph if and only if
if and only if
is a complete graph.
Consider the following two cases:
Case 1. . In this case
and there is nothing to prove.
Case 2. (
). We show that
.
Suppose not and so (in this case
). It follows from Theorem 2.2 and Proposition 3.1 that
where (as usual)
and
denote the numbers of vertices and edges in
, respectively.
For convenience, we let and
, and also let
Then clearly
(1)
(1)
We consider the following two subcases (we show that none of the following two subcases can happen):
Subcase 2.1. .
Then
Transposing and squaring yields
Replacing
by
, we get
(2)
(2) Obviously
, since
and
. Squaring again and simplifying yields
(3)
(3)
Therefore,
(4)
(4)
Therefore, if , then
is not a complete graph. Or if
, then
is not a complete graph
. On the other hand, if
for any non-complete graph
we always have
. Combining
and
we get:
if and only if
is not a complete graph. To put that another way,
if and only if
is a complete graph, a contradiction, since if
is a complete graph, then
.
Subcase 2.2. . In this case if
is non-complete graph, then
(*).
On the other hand by a similar argument of Subcase 2.1 for , if
, then
is not a complete graph (**). Combining (*) and (**) we have:
if and only if
is a complete graph, a contradiction. So, we must have
. Therefore, the assertion holds. □
Lemma 3.2
If is a connected graph
-cospectral with a multicone graph
, then it is either regular or bi-degreed with degrees
and
.
Proof
The result follows from Lemma 3.1 and Theorem 2.2. □
In the following, we show that any connected graph -cospectral with the multicone graph
is
.
Lemma 3.3
If is a connected graph
-cospectral with the multicone graph
, then
is
.
Proof
If , there is nothing to prove, since graph
in this case is a complete graph (see Theorem 2.4). Hence we suppose that
. In this case,
is bi-degreed (see Lemma 3.2). By Lemma 3.2 any vertex of
is either of degree
or
. Let
has
vertices (vertex) of degree
. Therefore, by Theorem 2.1 (iii) (sum of vertices degree of
that is sum of squares of the eigenvalues of
) and Proposition 3.1 we have:
By solving the equation we get
. This means that
has one vertex of degree
, say
and
vertices of degree
. It follows from Theorem 2.9 that
where
with
,
,
, and
.
As stated at the beginning of this lemma has one vertex of degree
and
vertices of degree
. This means that graph
has
vertices of degree
. In other words,
is a
-regular graph and it has
eigenvalues (vertices). It is clear that by removing the vertex
the number of edges that are deleted from graph
is
. On the other hand, the number of the closed walks of length 2 belonging to
is:
This means that the number of the closed walks of length 2 belonging to is
. (Or one can say that since
is a
-regular graph and it has
eigenvalues, so the number of the closed walks of length 2 belonging to
is
).
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 , we have:
where
and
are the eigenvalues of
. The roots are
and
. Therefore,
. Hence,
, and so
. □
Until now, we have considered only graphs -cospectral with the multicone graph
(windmill-like graphs with larger sails). The next theorem extends our result to the general multicone graph
.
Theorem 3.1
If is a connected graph
-cospectral with a multicone graph
, then
is
.
Proof
If the proof is clear. Take
. We perform the mathematical induction on
. For
, the proof follows from Lemma 3.3. Let the claim be true for
; that is, if
, then
, where
is an arbitrary graph
-cospectral with a multicone graph
. We show that the claim is true for
; that is, we show that if
, then
, where
is a graph. It is clear that
has one vertex and
edges more than
. By a similar argument that stated at the beginning of Lemma 3.3 one may deduce that
has
vertices of degree
and
vertices of degree
and also
has
vertices of degree
and
vertices of degree
. Hence we must have
, since by Lemma 3.2
is bi-degreed and has
vertices of degree
and
vertices of degree
. Now, the induction hypothesis completes the proof. □
It is well-known that the smallest non-isomorphic cospectral graphs are and
(see ). Note that
(the complement of the windmill
) is not a connected graph while
is connected. Thus, we see that
is not
. However, Abdollahi, Janbaz and Oboudi [Citation26] proved that if
, then
is
. A natural question is what happens with the complement of the general multicone graph
. We address this in the next section.
4 Graphs ![](//:0)
-cospectral with complements of multicone graphs ![](//:0)
![](//:0)
In this section we investigate the complements of the multicone graphs . Clearly, if
, then the multicone graph is just the complete graph
, and so its complement is
with spectrum
. Clearly no other graph has this spectrum. On the other hand, the case
is much more interesting. The complement of
is the union
. The adjacency spectrum is
. Our next theorem determines which graphs have this spectrum.
Theorem 4.1
Let be a graph with adjacency spectrum
.
is not connected if and only if
.
If
is connected if and only if
, where
and
are the two roots of the equation
.
Proof
(a) Assume that is disconnected. Then by Theorem 2.3, there is a complete multipartite graph
for which
, where
. We show that
. If
, then
has precisely three different eigenvalues (
has two distinct eigenvalues if and only if
, where
and
are natural numbers. Also note that
). So by Theorem 2.8
is a bipartite graph. Hence
, and so
. Therefore,
. If
, then
and
. The converse is clear.
(b) Assume that is connected. Then
cannot be regular, so by Theorem 2.6, it must be a complete bipartite graph
, for some
and
. The spectrum of
is known to be
(see, for example, [Citation32]). This is also the spectrum of
when
and
, that is, when
(and likewise
) satisfies
. The converse is straightforward. □
As a consequence of this theorem, we have the result that the complement of a multicone graph is not
. However, these are the only graphs in this family that are not, as our next theorem shows. Before presenting the theorem, we note that
, where
denotes the complete
-partite graph with each of the partite sets being of size
. We also note that the spectrum of this graph is
.
Theorem 4.2
For , graphs
are
.
Proof
Let . It follows from Theorem 2.6 that if
is connected, then it is a complete bipartite graph. Therefore, it follows from Theorem 2.8 that
, a contradiction. Hence
is disconnected. Now, by Theorem 2.3 there is a complete multipartite graph
for which
, where
. We claim that
must be regular. Suppose not and so, as before, by Theorem 2.6
must be a complete bipartite graph, and this is impossible. Thus,
must have at least three partite sets, and since it is regular, it must be
, and so
, establishing the result. □
5 Laplacian spectrum determination of multicone graphs ![](//:0)
![](//:0)
In this section, we consider the Laplacian spectrum of multicones. Recall that the Laplacian matrix of a graph is the matrix
, where
is the adjacency matrix of
and
is the degree matrix, and the Laplacian spectrum of
, denoted
, is the spectrum of
.
We begin with some general results of [16–19,37] on Laplacian spectra.
Theorem 5.1
Let and
be graphs with Laplacian spectra
and
, respectively. Then
(a) the Laplacian spectrum of the complement is
, and
(b) the Laplacian spectrum of the join is
.
Theorem 5.2
The order of a graph
is a Laplacian eigenvalue of
if and only if
is the join of two graphs.
The next result gives the Laplacian spectrum of multicone graphs .
Proposition 5.1
The Laplacian spectrum of multicone is:
Proof
It is clear that and so
. Now, By Theorem 5.1 (b) the proof is straightforward. □
Theorem 5.3
Multicone graphs are
.
Proof
If , the proof is clear. So, we consider
. The proof is by induction on
. By Proposition 2.1 the result is clearly true when
. Assume that the theorem holds for
; that is, if
, then
We show that if
, then
It follows from Theorem 5.2 that
and
are the join of two graphs. On the other hand,
has one vertex, say
and
edges more than
. By Theorem 5.1 (a)
and
. We know that a graph is
if and only if its complement is
. Obviously,
. On the other hand,
has only one vertex more than
. Therefore,
or
. 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 is
.
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
For all
and
, the connected multicone graph
is both
and
.
For all
and
with
, the graphs
are both
and
.
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. [Citation5] proved that the friendship graph is not
, and, as we observed earlier, neither is the complement of
, and these are the only exceptions.
Remark 1
For
, the friendship graph
is
and for any
,
is
.
For
, the friendship graph
is
and for any
,
is
.
Consider
and
that have the same signless Laplacian spectrum (see Corollary 2.2 of [Citation38] and Theorem 2.1 of [Citation38]) 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 (in contrast to the ordinary Laplacian
), with the corresponding determined by signless Laplacian spectrum. Friendship graphs are known to be
. Thus, we conclude with the following conjecture.
Conjecture 1
Multicone graphs , except in multicone graphs
, are
.
References
- BrouwerA.E., HaemersW.H. Spectra of Graphs Universitext 2012Springer New York
- Van DamE.R., HaemersW.H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373 2003 241–272
- Van DamE.R., HaemersW.H., Developments on spectral characterizations of graphs, Discrete Math., 309 2009 576–586
- BouletR., JouveB., The lollipop graph is determined by its spectrum, Electron. J. Combin., 15 2008 R74
- CioabäS.M., HaemersW.H., VermetteJ., WongW., Graphs with all but two eigenvalues equal to ±1, J. Algebraic Combin., 41 2015 887–897
- DoobM., HaemersW.H., The complement of the path is determined by its spectrum, Linear Algebra Appl., 356 2002 57–65
- HaemersW.H., LiuX.G., ZhangY.P., Spectral characterizations of lollipop graphs, Linear Algebra Appl., 428 2008 2415–2423
- LiuY., SunY.Q., On the second Laplacian spectral moment of a graph, Czechoslovak Math. J., 2 2010 401–410
- SharafdiniR., AbdianA.Z., Signless Laplacian determinations of some graphs with independent edges, Carpat. Math. Pub., 10 2018 185-196
- WangW., XuC., A sufficient condition for a family of graphs being determined by their generalized spectra, European J. Combin., 27 2006 826–840
- WangJ., BelardoF., HuangQ., BorovicaninB., On the two largest Q-eigenvalues of graphs, Discrete Math., 310 2010 2858–2866
- HararyF., KingC., MowshowitzA., ReadR., Cospectral graphs and digraphs, Bull. Lond. Math. Soc., 3 1971 321–328
- SchwenkA.J., Almost all trees are cospectral HararyF.New Directions in the Theory of Graphs1973Academic Press275–307
- ErdösP., RéyniA., SósV., T., On a problem of graph theory, Studia Sci. Math. Hungar., 1 1966 215–235
- WangJ., ZhaoH., HuangQ., Spectral characterization of multicone graphs, Czechoslovak Math. J., 62 2012 117–126
- AbdianA.Z., MirafzalS.M., On new classes of multicone graph determined by their spectrums, Algebr. Struct. Appl., 2 2015 23–34
- AbdianA.Z., Graphs which are determined by their spectrum, Konuralp J. Math., 4 2016 34–41
- AbdianA.Z., Two classes of multicone graphs determined by their spectra, J. Math. Ext., 10 2016 111–121
- AbdianA.Z., Graphs cospectral with multicone graphs Kw▽L(P), TWMS. J. Appl. Eng. Math., 7 2017 181–187
- A.Z. Abdian, The spectral determination of the multicone graphs Kw▽P, 2017. arXiv preprintarXiv:1703.08728.
- AbdianA.Z., MirafzalS.M., The spectral characterizations of the connected multicone graphs Kw▽LHS and Kw▽LGQ(3,9), Discrete Math. Algorithms Appl., 10 2018 1850019
- AbdianA.Z., MirafzalS.M., The spectral determinations of the connected multicone graphs Kw▽mP17 and Kw▽mS, Czechoslovak Math. J.2018 1–14 10.21136/CMJ.2018.0098-17
- A.Z. Abdian, A. Behmaram, G.H. Fath-Tabar, Graphs determined by signless Laplacian spectra, AKCE Int. J. Graphs and Combin.,http://dx.doi.org/10.1016/j.akcej.2018.06.009.
- MirafzalS.M., AbdianA.Z., Spectral characterization of new classes of multicone graphs, Stud. Univ. Babe’s-Bolyai Math., 6232017 275–286 10.24193/subbmath.2017.3.01
- MirafzalS.M., AbdianA.Z., The spectral determinations of some classes of multicone graphs, J.Discrete Math. Sci. Crypt., 2112018 179–189
- AbdollahiA., JanbazS., OubodM.R., Graphs cospectral with a friendship graph or its complement, Trans. Combin., 2 2013 37–52
- CvetkovićD., RowlinsonP., SimićS. An Introduction to the Theory of Graph Spectra London Mathematical Society Student Texts 2010Cambridge Univ. Press
- OboudiM.R., On the third largest eigenvalue of graphs, Linear Algebra Appl., 503 2016 164–179
- OboudiM.R., Characterization of graphs with exactly two non-negative eigenvalues, Ars Mathematica Contemporanea, 12 2016 271–286
- HongY., ShuJ., FangK., A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B, 81 2001 177–183
- WangJ., HuangQ., Spectral characterization of generalized cocktail-party graphs, J. Math. Res. Appl., 32 2012 666–672
- KnauerU., Algebraic Graph Theory, Morphisms, Monoids and Matrices 2011De Gruyter
- BapatR.B., Graphs and Matrices 2010Springer-Verlag New York
- ChengX.M., GreavesG.R.W., KoolenJ.H., Graphs with three eigenvalues and second largest eigenvalue at most 1 http://de.arxiv.org/abs/1506.02435v1
- Van DamE.R., Nonregular graphs with three eigenvalues, J. Combin. Theory Ser. B, 7321998 101–118
- RowlinsonP., The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math., 1 2007 445–471
- MerrisR., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197 1994 143–176
- LiuX., LuP., Signless Laplacian spectral characterization of some joins, Electron. J. Linear Algebra, 3012015 30