![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
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.
MSC(2010):
1. Introduction
In [Citation25] and [Citation43], 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 (n is sometimes called the order of G) and the vertex set
will be
and edge set E(G). Concepts not defined here can be found in the books [Citation17, Citation20, Citation24]. The complement of a graph G is denoted by
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
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,
Let be the (0, 1)-adjacency matrix of G and let
be the diagonal matrix with the i’th diagonal entry being the degree di of the vertex vi. The matrix
is called the Laplacian matrix of G. Since both matrices
and
are real and symmetric, their eigenvalues are all real. Let
be the eigenvalues of
and
the eigenvalues of
The spectral radius of G is the largest eigenvalue of its adjacency matrix is denoted by
The adjacency spectrum
of G consists of the adjacency eigenvalues (together with their multiplicities), and similarly the Laplacian spectrum
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 [Citation38, Citation39] 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 [Citation1–16, Citation22, Citation26–30, Citation32, Citation34–36, Citation38, Citation39] and the references cited therein). Van Dam and Haemers [Citation38] 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 [Citation22, Citation31]. For more on the background of the question” Which graphs are determined by their spectrum?”, we refer to [Citation38]. The spectral characterization of certain multicone graphs was explored by Wang, Zhao and Huang [Citation42], who asserted that friendship graphs Fn (certain special classes of multicone graphs) are adjacency-spectrum determined. In addition, Wang, Belardo, Huang and Borovićanin [Citation40] proposed such conjecture on the adjacency spectrum of Fn. This conjecture inspired activity on the spectral characterization of this family of graphs. Finally, Cioabä and et al. [Citation19] proved that if then the friendship graph Fn is DS with respect to its adjacency spectrum. Abdian and Mirafzal [Citation11] characterized new classes of multicone graphs that are DAS. Abdian [Citation1] 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 [Citation2] and [Citation3], it was shown that the multicone graph
for G being the Paley graph P17 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 [Citation4, Citation12].
We believe that there are some gaps in the proofs in [Citation42]. 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 ([Citation42]) to characterize new classes of multicone graphs, which is what we want to do here. Conjectures 1 and 2 of Wang, Zhao and Huang [Citation42] are not true, and there are counterexamples for them (see the first paragraph after Corollary 2 of [Citation19]). In Theorem 3 (ii) of [Citation42] first the minimum degree of a graph cospectral to a graph belonging to (classes of bi-degreed graphs with degree sequence δ and
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
will not be effective or useful. For some multicone graphs which have been characterized, see [Citation1–4, Citation8, Citation9, Citation11–13, Citation28, Citation29, Citation34].
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
([Citation12, Citation13, Citation20]). The following can be obtained from the adjacency spectrum and Laplacian spectrum of a graph :
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, denotes the characteristic polynomial of graph G.
Theorem 2.1
([Citation20, Citation42]). If for i = 1, 2, Gi has order ni and is ri-regular, then the characteristic polynomial of the join is
Theorem 2.2
([Citation23, Citation42]). Let G be a graph with n vertices, m edges, minimum degree δ, and spectral radius . Then
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
For further information about the inequality in this theorem, we refer the reader to [Citation42], 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
([Citation12, Citation27]). Let G and H be graphs with Laplacian spectra and
, respectively. Then the Laplacian spectrum of
is
and that of
is
Theorem 2.4
([Citation12, Citation27]). 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
([Citation24]). For a graph G, the following statements are equivalent
G is d-regular.
, the average vertex degree.
is an eigenvector for
Proposition 2.1
([Citation12, Citation20]). If j is a vertex of graph G, then , where k and αij are the number of distinct eigenvalues and the main angles (see [Citation33]) of graph G, respectively.
Proposition 2.2
([Citation39]). If G is a disconnected graph determined by the Laplacian spectrum, then so is the cone over G;, of the graph
Theorem 2.6
([Citation12, Citation37]). If G is a non-regular graph with three distinct eigenvalues , then the following hold
G has diameter2.
If
is not an integer, then G is a complete bipartite graph.
with equality if and only if G is complete bipartite.
with equality if and only if G is the path of length2.
Theorem 2.7
([Citation41]). 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 are natural numbers. In addition, when
we always assume that G is connected since some classes of disconnected graphs are not DAS. Some examples are the following:
but
but
but
However, if a graph cospectral with the multicone graph 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 is either regular or bi-degreed.
Proposition 3.1.
Let G be a graph cospectral with the multicone graph , and let
and
. Then
is:
if s is even, and
if s is odd.
Proof.
It is well-known that the s-cycle Cs has eigenvalues where
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 , then
Proof.
Let 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
From Theorem 2.2 and Proposition 3.1 it follows that
where (as usual) n and m denote the numbers of vertices and edges in G.
For convenience, we let and
and also let
By replacing the new notations we have
or
Then clearly
We consider two cases:
Case 1:
x < 0. In this case, for any non-complete graph G we always have (1). It is easy and straightforward to see that
since
Transposing and squaring yields
Replacing q(x) by
we get
Obviously
By squaring the last inequality we get
or
or
Therefore,
or
By simplifying this inequality we get
or
So, if then G cannot be a complete graph (2). Combining (1) and (2) we get:
if and only if G is not a complete graph. To put that another way, G is a complete graph if and only if
which is a contradiction, since if G is a complete graph, then
Case 2:
In the same way as Case 1, we can conclude that if G is complete, then a contradiction. So we must have x = 0. Therefore, the claim holds. □
Lemma 3.2.
If G is a connected graph and . Then G is either regular or bi-degreed with degrees
and w + 2.
Proof.
This follows from Lemma 3.1 together with Theorem 2.2. □
3.1. Graphs cospectral with the multicone graphs ![](//:0)
![](//:0)
In this section, we show that any graph cospectral with the multicone graph is DAS.
Lemma 3.3.
If G is a connected graph and , 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 or
By Lemma 3.2, it is clear that G has one vertex of degree rs, say vj. We consider two cases:
Case 1:
s is even. From Proposition 2.1, it follows that
where
and
).
Case 2:
s is odd. As in Case 1 from Proposition 2.1, it follows that
where
and
).
Now, from Lemma 3.2, it follows that is a 2-regular graph of order s. Therefore, we conclude that
is either
or
Hence
So,
which completes the proof. □
Up to now, we have shown that the multicone graph is DAS. A natural question is what happens for multicone graph
when w > 1. We answer this question in the following theorem.
Theorem 3.1.
Any connected graph cospectral with the multicone graph 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 then
We show that the claim is true for w + 1. We show that
implies that
Obviously, H has one vertex and w + rs edges more than H. By Lemma 3.2, G has w vertices of degree
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
So, we must have
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 By Lemma 3.2, G has a subgraph F that is regular of degree
In other words,
where H is a subgraph of G. Now, we remove the vertices of the complete graph Kw 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,
is either
or
Hence
and the result follows. □
3.2. Some classes of graphs ![](//:0)
and their adjacency spectra
In this section, we show that the complements of the multicone graphs are DAS.
Theorem 3.2.
If G is a graph with , then
Proof.
Assume that If r = 1, there is nothing to prove. If r = 2, then Theorem 2.7 implies that
where G1 is a complete multipartite graph and c is a natural number. On the other hand, it follows from Theorem 2.6 that G1 is a complete bipartite graph. Therefore,
Hence
Therefore, we can suppose that
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
where d is a natural number. Also, it is clear that G1 has exactly three distinct eigenvalues. Now, for the sake of contradiction, we suppose that G1 is not regular. From Theorem 2.6 it follows that G1 is a complete bipartite graph and so G is itself bipartite, and this is a contradiction. Hence G1 is regular and so
Now, from Theorem 2.7, it follows that G1 is a multipartite graph and so must be congruent to the r-partite graph
with each partite set having three vertices. Therefore
which proves the result. □
4. Laplacian spectral determinations of multicone graphs ![](//:0)
![](//:0)
In this section, we show that with a few exceptions for small values of w, r and s ( and
see [Citation43], ), then the multicone graphs
are DLS.
Theorem 4.1.
The multicone graphs are DLS, if
and
Proof.
It is well-known that where
All multiplicities are 2, except that of 0 and possibly 4. We use induction on
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,
implies that
We show that the claim is true for w + 1, that is, we show that
implies that
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
Therefore, we must have
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 ![](//:0)
![](//:0)
A graph G is called perfect if its chromatic number is equal to the order of its largest complete subgraph
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, Cn for
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 [Citation18]). Here, we show that some graphs that are adjacency or Laplacian cospectral with
must be perfect.
Theorem 4.2.
A connected graph G that is adjacency cospectral with the multicone graph is perfect and so is its complement
if and only if s = 3 or s is even.
Proof.
: This follows at once since if s is odd, then clearly G has an odd hole.
It is easy to see that G cannot have an odd hole. Suppose that it has an odd antihole, that is, it contains
as an induced subgraph where k is odd and at least 5. Hence
must contain Ck as an induced subgraph. It is easy to see that this cycle must be contained in
which is the join
of the complements of r cycles Cs, and this is clearly impossible. □
Theorem 4.3.
A graph G that is Laplacian cospectral with the multicone graph is perfect
and so is its complement
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 are both DAS (as connected graphs) and DLS (
and
). We also show that the multicone complements
are DAS, and from [Citation11] (Theorem 5.2) it follows that so are the graphs
We believe that these results can be extended and make the following conjectures:
Conjecture 1. The multicone complement graphs are DAS.
Conjecture 2. The multicone graphs are DQS.
Disclosure statement
No potential conflict of interest was reported by the author(s).
References
- Abdian, A. Z. (2016). Graphs which are determined by their spectrum. Konuralp J. Math. 4: 34–41.
- Abdian, A. Z. (2016). Two classes of multicone graphs determined by their spectra. J. Math. Ext. 10: 111–121.
- Abdian, A. Z. (2017). Graphs cospectral with multicone graphs. Kw∇L(P), TWMS. J. Appl. Eng. Math. 7: 181–187.
- Abdian, A. Z. (2017). The spectral determination of the multicone graphs. Kw∇P, arXiv preprint. 1703.08728.
- Abdian, A. Z. (2023). Bell graphs are determined by their Laplacian spectra. Kragujevac J. Math. 47: 203–211.
- Oboudi, M. R., Abdian, A. Z., Ashrafi, A. R., and Beineke, L. W., (2021). Laplacian spectral determination of path-friend-ship graphs. AKCE Int. J. Graphs Comb. DOI: 10.1080/09728600.2021.1917321
- Abdian, A. Z., Ashrafi, A. R., Brunetti, M. (2020). Signless Laplacian spectral characterization of roses. Kuwait J. Sci. 47: 12–18.
- Abdian, A. Z., Behmaram, A., Fath-Tabar, G. H. (2020). Graphs determined by signless Laplacian spectra. AKCE Int. J. Graphs Comb. 17(1): 45–50.
- Abdian, A. Z., Beineke, L. W., Oboudi, M. R., Behmaram, A.,Thulasiraman, K., Alikhani, S., Zhao, K. (2020). On the spectral determinations of the connected multicone graphs Kr∇sKt. AKCE Int. J. Graphs Comb.17(1).
- Abdian, A. Z., Fath-Tabar, G. H., Moghaddam, M. R. (2020). The spectral determination of the multicone graphs Kw∇C with respect to their signless Laplacian spectra. J. Algebraic Systems 7(2): 131–141.
- Abdian, A. Z., Mirafzal, S. M. (2015). On new classes of multicone graph determined by their spectrums. Alg. Struct. Appl. 2: 23–34.
- Abdian, A. Z., Mirafzal, S. M. (2018). The spectral characterizations of the connected multicone graphs Kw∇LHS and Kw∇LGQ(3,9). Discrete Math. Algorithms Appl. 10: 1850019.
- Abdian, A. Z., Mirafzal, S. M. (2018). The spectral determinations of the connected multicone graphs Kw∇mP17 and Kw∇mS. Czech. Math. J. 68(4): 1091–1104.
- Abdian, A. Z., Moez, A. M. (2019). The spectral determinations of the join of two friendship graphs. Honam J. Math. 41: 67–87.
- Abdian, A. Z., Thulasiraman, K., Zhao, K. (2020). The spectral characterization of the connected multicone graphs Kw∇mKn,n. AKCE Int. J. Graphs Comb.17(1).
- Abdian, A. Z., Ziaie, M. (2019). Signless Laplacian spectral determinations of the starlike trees ST(n;d1) and the double starlike trees Hn(p;p). ARS Comb. In Press.
- Bapat, R. B. (2010). Graphs and Matrices, Vol. 27. London: Springer.
- Brandstädt, A., Le, V. B., Spinrad, J. P. (1999). Graph classes: A survey. SIAM Monographs Discrete Math. Appl.
- Cioabă, S. M., Haemers, W. H., Vermette, J. R., Wong, W. (2015). The graphs with all but two eigenvalues equal to ±1. J. Algebr. Comb. 41(3): 887–897.
- Cvetković, D., Rowlinson, P., Simić, S. (2010). An Introduction to the Theory of Graph Spectra. Cambridge: Cambridge University Press, pp. 230–231.
- Doob, M., Haemers, W. H. (2002). The complement of the path is determined by its spectrum. Linear Algebra Appl. 356(1-3): 57–65.
- Günthard, H. H., Primas, H. (1956). Zusammenhang von Graph Theory und Mo-Theorie von Molekeln mit Systemen konjugierter Bindungen. HCA 39(6): 1645–1653.
- Hong, Y., Shu, J., Fang, K. (2001). A sharp upper bound of the spectral radius of graphs. J. Combin., Theory Ser. B 81(2): 177–183.
- Knauer, U. (2011). Algebraic graph theory: morphisms, monoids and matrices. de Gruyters Studies in Mathematics, de Gruyters 41.
- Liu, M.-H. (2012). Some graphs determined by their (signless) Laplacian spectra. Czech Math. J. 62(4): 1117–1134.
- Liu, Y., Sun, Y. Q. (2010). On the second Laplacian spectral moment of a graph. Czech Math. J. 60(2): 401–410.
- Merris, R. (1994). Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197–198: 143–176.
- Mirafzal, S. M., Abdian, A. Z. (2017). Spectral characterization of new classes of multicone graphs. Stud. Univ. Babes-Bolyai Math. 62(3): 275–286.
- Mirafzal, S. M., Abdian, A. Z. (2018). The spectral determinations of some classes of multicone graphs. J. Discrete Math. Sci. Cryptogr. 21(1): 179–189.
- Oboudi, M. R., Abdian, A. Z. (2020). Peacock graphs are determined by their Laplacian spectra. Iran. J. Sci. Technol. Trans. Sci. 44(3): 787–790.
- Peisert, W. (2001). All self-complementary symmetric graphs. J. Algebra 240(1): 209–229.
- Pouyandeh, S., Moez, A. M., Abdian, A. Z. (2019). The spectral determinations of connected multicone graphs. Kw∇mCP(n) Aims Math., 4: 1348–1356.
- Rowlinson, P. (2007). The main eigenvalues of a graph: a survey. Appl. Anal. Discrete Math. 1(2): 455–471.
- Sharafdini, R., Abdian, A. Z. (2018). Signless Laplacian determinations of some graphs with independent edges. Carpathian Math. Publ. 10(1): 185–191.
- Sharafdini, R., Abdian, A. Z. (2021). Signless Laplacian determination of path-friendship graphs Acta Math. Univ. Comenianae. In Press.
- Sharafdini, R., Abdian, A. Z., Behmaram, A. (2020). Signless laplacian determination of a family of double starlike trees. Ukrainian Math. J. In Press.
- Van Dam, E. R. (1998). Nonregular graphs with three eigenvalues. J. Combin. Theory, Ser. B 73(2): 101–118.
- van Dam, E. R., Haemers, W. H. (2003). Which graphs are determined by their spectrum? Linear Algebra Appl. 373: 241–272.
- van Dam, E. R., Haemers, W. H. (2009). Developments on spectral characterizations of graphs. Discrete Math. 309(3): 576–586.
- Wang, J., Belardo, F., Huang, Q., Borovićanin, B. (2010). On the two largest Q-eigenvalues of graphs. Discrete Math. 310(21): 2858–2866.
- Wang, J., Huang, Q. (2012). Spectral characterization of generalized cocktail-party graphs. J. Math. Res. Appl. 32: 666–672.
- Wang, J., Zhao, H., Huang, Q. (2012). Spectral characterization of multicone graphs. Czech Math. J. 62(1): 117–126.
- Zhang, Y., Liu, X., Yong, X. (2009). Which wheel graphs are determined by their Laplacian spectra? Comput. Math. Appl. 58(10): 1887–1890.