Abstract
A multicone graph is defined to be the join of a clique and a regular graph. Let , and be natural numbers, and let and denote a complete graph and a complete bipartite graph, respectively. In this work, it is proved that connected multicone graphs , natural generalizations 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. Furthermore, we prove that any graph cospectral with a multicone graph is perfect with respect to its adjacency (Laplacian) spectra. At the end of the paper, we pose two problems for further research.
1 Introduction
Throughout the paper, except in Section 3.2, is a connected undirected simple graph with and . In this section we recall some definitions that will be used in the paper. For terminology and notation not defined here, we refer the readers to Citation[1–4]. The notation is used to denote as the neighbors of vertex . The degree of vertex , written , is . We use and to indicate the maximum and minimum degrees of , respectively. A graph is called bidegreed if the set of degrees of vertices consists of exactly two distinct elements. Let the adjacency matrix, degree matrix of be , , respectively. The Laplacian matrix of is and the signless Laplacian matrix of is . Clearly, and are real symmetric matrices. We denote the characteristic polynomial of by . The adjacency spectrum of , denoted by , is the multiset of eigenvalues of . Since is symmetric, its eigenvalues are real. The union of two graphs and is the graph whose vertex set is and whose edge set is . We denote this graph by . The join of two graphs and , denoted by , is created by adding edges between and so that every vertex in is adjacent to every vertex in . of eigenvalues of is called the adjacency spectrum of , where denote the multiplicity of eigenvalue (For the definition is similar). A graph is said to be determined by its spectrum or DS for short, if there is no non-isomorphic graph with the same adjacency (respectively, Laplacian) spectrum.
Determining which graphs are DS is a hard problem. About the background of the research question “which graph are determined by their spectrum?”, one can refer to Citation[5,6]. The authors in Citation[5] conjectured that nearly all graphs are determined by their spectra. However, the set of graphs that are known to be determined by their spectra is very small. Hence finding classes of graphs that are determined by their spectra can be an interesting and significant problem. A spectral characterization of some classes of multicone graphs was studied in Citation[7]. The authors Citation[7,8] conjectured that friendship graph (see ) is DS with respect to their adjacency spectra. This conjecture caused some activities on the adjacency spectral characterization of . Eventually, the authors Citation[9] proved that if is a graph cospectral with a friendship graph and , then is isomorphic to . Abdian and Mirafzal [Citation10] characterized new classes of multicone graphs. These authors proved that the join of an arbitrary complete graph with an arbitrary Cocktail-Party graph is determined by its adjacency spectra as well as its Laplacian spectra. They also conjectured that these multicone graphs are determined by their signless Laplacian spectra. Abdian [Citation11] characterized two classes of multicone graphs and showed that the join of an arbitrary complete graph and the generalized quadrangle graph or is determined by both its adjacency and its Laplacian spectra. This author also proposed four conjectures about adjacency spectrum of complement and signless Laplacian spectrum of these multicone graphs. In [Citation12], the author showed that multicone graphs and are determined by their adjacency and their Laplacian spectra, where and denote the Paley graph of order 9 and the Schläfli graph, respectively. Also, this author conjectured that these multicone graphs are determined by their signless Laplacian spectra. For seeing some multicone graphs which have been characterized so far refer to [10–22].
The organization of the paper is as follows. In Section 2, we review some basic information and preliminaries. In Section 3 (Sections 3.0.1 and 3.0.2), we show that any connected graph cospectral with one of multicone graphs is determined by its adjacency spectra. In Section 3.1, we prove that these graphs are determined by their Laplacian spectra. In Section 3.2, we prove that the complement of these graphs is DS with respect to their adjacency spectra. In Section 3.3, we show that any graph cospectral with one of these graphs must be perfect. In Section 4, we review our results in the previous sections. In conclusion we propose two conjectures for further research.
2 Notation and preliminaries
In this section, we give some results which will play a crucial role throughout the paper.
Theorem 2.1
Citation[2,7] 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.
Theorem 2.2
Citation[18,23] A graph has exactly one positive eigenvalue if and only if it is a complete multipartite graph with possibly some isolated vertices.
Theorem 2.3
Citation[3] 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.4
Citation[1] If is an-regular graph with eigenvalues , then are the eigenvalues of the complement of .
Theorem 2.5
[Citation23] 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) .
Theorem 2.6
Citation[2] For , let be an-regular graph of order . Then the characteristic polynomial of their join is
Theorem 2.7
Citation[3,18] 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) .
Theorem 2.8
Citation[2] 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
Citation[6] 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.
Theorem 2.9
[Citation24] 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 2.10
Citation[10–13,24] The order of a graph is a Laplacian eigenvalue of if and only if is the join of two graphs.
Remark 1
It is well-known that is not determined by its adjacency spectrum (see the first paragraph after Corollary 2 of Citation[9]). Therefore, in the case that , we always suppose that is connected.
3 Main results
The purpose of this section is to show that any graph cospectral with a multicone graph is regular or bidegreed.
3.0.1 Connected graphs cospectral with a multicone graph
Proposition 3.1
The adjacency spectrum of multicone graph is
where and .
Proof
By Theorem 2.6 and , the proof is completed.□
Lemma 3.1
Let be a connected graph cospectral with a multicone graph . Then .
Proof
Let , where is an integer number. First, it is clear that in this case the equality in Theorem 2.1 occurs, if and only if . We claim that . By contrary, we suppose that . It follows from Theorem 2.1 together with Proposition 3.1 that where the integer numbers and denote the number of edges and the number of vertices of the graph , respectively.
For convenience, we let and , and also let .
Then clearly
We consider two cases:
Case 1. .
It is easy and straightforward to see that , since .
Transposing and squaring yields
Replacing by , we get Obviously . Squaring again and simplifying yields (1) (1)
Therefore, (2) (2)
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. But, if is a complete graph, then . Hence, we have and so , a contradiction.
Case 2. . In this case if is non-complete graph, then (*).
On the other hand by a similar argument of Case 1 for , if , then is not a complete graph (**). Combining (*) and (**) we have: if and only if is a complete graph or is a complete graph if and only if , a contradiction. So, we must have . Therefore, the assertion holds. □
In the next lemma we show that if or , then any graph cospectral with a multicone graph must be bidegreed.
Lemma 3.2
Let be a connected graph cospectral with a multicone graph . Then is either regular or bidegreed, in which any vertex of is of degree or .
Proof
By Theorems 2.1, 2.3 and Lemma 3.1 the proof is completed. □
In the following, we show that multicone graphs are DS with respect to their adjacency spectrum.
3.0.2 Connected graphs cospectral with the multicone graph
Lemma 3.3
Any connected graph cospectral with the multicone graph is isomorphic to .
Proof
Let be a graph cospectral with a multicone graph . By Lemma 3.2, has one vertex of degree , say . Now, , where , , , and and is the characteristic polynomial of . It follows from Theorem 2.8 that , where We know that has roots (eigenvalues). Also, it is clear that is a -regular graph (see Lemma 3.2). It is easy and straightforward to see that by removing the vertex the number of edges and the number of triangles that are removed of graph are equal to and , respectively. Now, by computing the number of the closed walks of lengths 1, 2 and 3 belonging to we have: where , and are eigenvalues of . By solving the above equations, , and . So, . Obviously, graph with adjacency spectrum is a regular graph and also it has three distinct eigenvalues. Therefore, is a strongly regular graph. So, (see Proposition 10 (i) of Citation[5]). Hence . Thus the result follows. □
Hitherto, we have shown that multicone graphs are DS. The natural question is; what happens for multicone graphs ? we answer this question in the next theorem.
Theorem 3.1
Let be a connected graph. If , then .
Proof
We solve the problem by induction on . If , there is nothing to prove. Let the claim be true for ; that is, if , then , where is an arbitrary graph cospectral with a multicone graph . We show that , implies that . By Lemma 3.2 has vertices of degree and vertices of degree . Also from this lemma follows that has vertices of degree and vertices of degree . On the other hand, has one vertex and edges more than . So, we must have . Consequently, the inductive hypothesis completes the proof.□
In the following, we present an alternate proof of Theorem 3.1.
Alternate proof of Theorem 3.1
By Lemma 3.2, has graph as its subgraph in which degree of any vertex of is . In other words, , where is a subgraph of . Now, we remove vertices of and we consider other vertices. Degree of graph consisting of these vertices is , say . is regular and its degree of regularity is and multiplicity of is . By Theorem 2.6, . Now, Theorem 2.2 implies that . This completes the proof. □
3.1 Connected graphs cospectral with a multicone graph with respect to Laplacian spectrum
In this subsection, we prove that any graph cospectral with a multicone graph is DS with respect to its Laplacian spectrum.
Theorem 3.2
Let be a graph. If , then .
Proof
It is clear that . We solve the problem by induction on . If , by Proposition 2.1 the proof is completed. Let the problem be true for , that is, if , then , where is an arbitrary graph cospectral with a multicone graph . We show that implies that , where is a graph. It follows from Theorem 2.10 that and are the join of two graphs. On the other hand, and also has one vertex and edges more than .Therefore, we must have . Now, the inductive hypothesis completes the proof. □
Corollary 3.1
Friendship graphs are DS with respect to their Laplacian spectrum.
In the following, we show that any graph cospectral with a complement of multicone graph is DS with respect to its adjacency spectrum. Also, we show that complement of multicone graph is DS with respect to its adjacency spectrum, where .
3.2 Graphs cospectral with a complement of multicone graph
Proposition 3.2
Let be cospectral with a complement of multicone graph . Then .
Proof
By Theorem 2.4 the proof is straightforward. □
Lemma 3.4
Let be a graph and . Then .
Proof
Firstly, we show that is disconnected. By contrary, we suppose that is connected. It is clear that cannot be regular. In this case, we conclude from Theorem 2.5 that is a complete bipartite graph. By Theorem 2.2, and so . This is a contradiction. Therefore, is disconnected. Hence , where () are connected components of . We show that does not have distinct three eigenvalues. By contrary, we suppose that has three distinct eigenvalues. We consider two cases:
Case 1. is non-regular.
In this case, Theorem 2.5 implies that is a complete bipartite graph, that is, , where and , are natural numbers. Hence and also and so cannot have three distinct eigenvalues.
Case 2. is regular.
It is clear has exactly one positive eigenvalue. On the other hand, we conclude from Theorem 2.2 that , where is a complete multipartite graph. Obviously, and so and so cannot have three distinct eigenvalues. By what has been proved hitherto, any connected component of has either one or two eigenvalue(s). In other words, any connected component of is either isolated vertex or a complete graph. Hence
Theorem 3.3
Any graph cospectral with is isomorphic to .
Proof
If graph is cospectral with the , then . Now, By Lemma 3.4 the proof is straightforward. □
In , it is proved that any graph cospectral with a complement of friendship graph , , is DS, where . Now, we generalize this fact and we show that if , then complement of multicone graph , , is DS with respect to its adjacency spectrum.
Proposition 3.3
Let be a graph cospectral with the graph .
if and only if is disconnected.
Proof
() Is trivial.
() By Lemma 2.4, is a bipartite graph. By Theorem 2.2 , where is a subgraph of . By Theorem 2.10 is a complete bipartite graph and so . This completes the proof.□
Proposition 3.4
Let be a graph cospectral with .
is connected if and only if and .
Proof
Is trivial.
By Theorem 2.5 the proof is completed. □
Theorem 3.4
Let be a graph and . Then is DS, where .
Proof
If , there is nothing to prove. Hence we let . It follows from Theorem 2.5 that is not connected and also Theorem 2.2 implies that , where is a natural number. We show that is a regular graph. By contrary, we suppose that is a non-regular graph. It follows from Theorem 2.5 that is a complete bipartite graph and so is a bipartite graph. This is a contradiction, since contains at least a triangle. Hence is a regular graph and so . Now, from Theorem 2.2 we conclude that is a multibipartite graph. Hence and so . □
Suppose and are chromatic number and clique number of graph , respectively. A graph is perfect if for every induced subgraph of . It is proved that a graph is perfect if and only if is Berge; that is, it contains no odd hole or antihole as induced subgraph, where odd hole and antihole are odd cycle, for , and its complement, respectively. Also, in Lovásaz proved that, a graph is perfect if and only if its complement is perfect [Citation25].
3.3 Some graphical results on multicone graphs
Theorem 3.5
Let graph be a graph cospectral with a multicone graph . Then and are perfect.
Proof
This follows Theorem 3.1 and the fact that is perfect .□
Theorem 3.6
Let . Then and are perfect.
Proof
This follows Theorem 3.2 and the fact that is perfect. □
4 Concluding remarks and open problems
In this work, it is proved that multicone graphs are DS with respect to their adjacency spectra as well as their Laplacian spectra. Also, we shown that if , then any graph cospectral with a complement of multicone graph is DS with respect to its adjacency spectra. Since multicone graphs are a natural generalization of friendship graphs and the friendship graphs are DS with respect to their signless Laplacian spectra, we pose two problems for further study.
Conjecture 1
Any graph cospectral with a complement of multicone graph is DS, where .
Conjecture 2
Multicone graphs are DS with respect to their signless Laplacian spectrum.
References
- BapatR.B., Graphs and Matrices2010Springer-VerlagNew York
- CvetkovićD.RowlinsonP.SimićS.An Introduction to theory of graph SpectraLondon Mathematical Society Student Texts vol. 752010Cambridge University PressCambridge
- KnauerU.Algebraic Graph Theory, Morphism, Monoids and Matricesde Gruyters Studies in Mathematics vol. 412011Walter de Gruyters and Co.Berlin and Boston
- ThulasiramanK.ArumugamS.BrandstädtA.NishizekiT., Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, Vol. 342016CRC Press
- van DamE.R.HaemersW.H., Which graphs are determined by their spectrum? Linear Algebra Appl. 3732003 241–272
- van DamE.R.HaemersW.H., Developments on spectral characterizations of graphs Discrete Math. 3092009 576–586
- WangJ.F.ZhaoH.HaungQ., Spectral charactrization of multicone graphs Czech. Math. J. 1372012 117–126
- WestD.B., Introduction to Graph Theory2001Upper Saddle River: Prentice hall
- CioabäS.M.HaemersW.H.VermetteJ.R.WongW., The graphs with all but two eigenvalues equal to ±1 J. Algebr. Combin. 412013 887–897
- AbdianA.Z.MirafzalS.M., On new classes of multicone graph determined by their spectrums Alg. Struc. Appl. 22015 23–34
- AbdianA.Z., Graphs which are determined by their spectrum Konuralp J. Math. 42016 34–41
- AbdianA.Z., Two classes of multicone graphs determined by their spectra J. Math. Ext. 102016 111–121
- AbdianA.Z., Graphs cospectral with multicone graphs Kw▽L(P) TWMS. J. Appl. Eng. Math. 72017 181–187
- A.Z. Abdian, The spectral determination of the multicone graphs Kw▽P, arXiv preprintarXiv:1703.08728 (2017).
- AbdianA.Z.MirafzalS.M., The spectral characterizations of the connected multicone graphs Kw▽LHS and Kw▽LGQ(3,9) Discrete Math. Algorithm Appl. (DMAA) 102018 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, The spectral determinations of the multicone graphs Kw▽mCn, arXiv preprintarXiv:1703.08728.
- AbdianA.Z.et al., On the spectral determinations of the connected multicone graphs Kr▽sKt AKCE Int. J. Graphs Combin.2019. 10.1016/j.akcej.2018.11.002(in press)
- A.Z. Abdian, A. Behmaram, G.H. Fath-Tabar, Graphs determined by signless Laplacian spectra, AKCE Int. J. Graphs and Combin.https://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. 62 3 2017 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. 21 1 2018 179–189
- SharafdiniR.AbdianA.Z., The spectral determinations of some classes of multicone graphs Carpathian Math. Publ 10 1 2018 185–196
- WangJ.HuangQ., Spectral characterization of generalized cocktail-party graphs J. Math. Res. Appl. 322012 666–672
- MerrisR., Laplacian matrices of graphs: a survey Linear Algebra Appl. 1971994 143–17696
- BrandstädtA.LeV.B.SpinradJ.P., Graph classes: a survey SIAM Monogr. Discrete Math. Appl.1999