Abstract
Let be a graph and be its adjacency matrix. The eigenvalues of are the eigenvalues of and form the adjacency spectrum, denoted by . In this paper, we introduce two new operations and , and describe the adjacency spectra of and of regular graphs , and arbitrarily graphs , in terms of their adjacency spectra. As the applications, we obtain some new integral spectrum graphs.
1 Introduction
All graphs considered in this paper are undirected, finite and simple graphs. Let be a graph with the vertex set . The adjacency matrix of is an matrix whose th entry, , is if the th vertex of is adjacent to the th vertex of and otherwise. The eigenvalues of are called the eigenvalues of and they form the adjacency spectrum of , denoted by . The properties of graph spectra and its applications were inducted in [Citation1]. In this paper, we follow [Citation2] for graph theoretic terminology and we only consider the adjacency spectrum of .
In [Citation3], Harary and Schwenk initiated the problem of finding (describing) all graphs with integral spectrum. In general, this problem seems to be intractable. Some special results were obtained only for certain classes of graphs (see e.g. [4–11Citation[4]Citation[5]Citation[6]Citation[7]Citation[8]Citation[9]Citation[10]Citation[11]]).
The of graphs and , denoted by , is the graph with vertex set , and is adjacent to whenever and , or and .
Let and be copies of graphs and , respectively, is an arbitrary graph. The first operation of , and is obtained by making the Cartesian product of two graphs and , thus produces copies () of , then makes joins . Note that if , the first operation is the Indu–Bala product in [Citation12]. The second operation of , , and is obtained by making the Cartesian product of two graphs and , produces copies () of and making the Cartesian product of two graphs and , produces copies () of , then makes joins . and are shown in .
In this paper, we describe the adjacency spectra of and for regular graphs , and arbitrarily graphs , in terms of their adjacency spectra. By using these results, we can construct new integral spectrum graphs.
2 Preliminaries
In this section, we present some lemmas which will be used later in order to prove our main results.
The Kronecker product of matrices and , denoted by , is defined to be the partition matrix . See [Citation1]. In cases where each multiplication makes sense, we have .
This implies that for nonsingular matrix and , . Recall also that for square matrices and of order and , respectively. .
If is nonsingular, then
Let be the column vector of size with all entries equal to one, a column zero vector of size , and the identity matrix of order . Let be the th unit column vector of size for . For a vertex of a graph , let be the degree of vertex in . For vertices and in a graph, means that is adjacent to .
Lemma 2.1
[Citation1]
If the graph has vertices and the adjacency matrix , and the graph has vertices and the adjacency matrix , then the adjacency matrix of the Cartesian product of both graphs is given by .
Lemma 2.2
[Citation1]
Let and be square matrices of orders and , respectively, with eigenvalues and . Then the eigenvalues of are . Moreover, if is an eigenvector of affording and is an eigenvector of affording , then is an eigenvector of affording .
3 The adjacency spectra of and
First we will describe the spectrum of for regular graphs , and an arbitrary graph in terms of their spectra.
Theorem 3.1
For , let be an regular graph with vertices and be the eigenvalues of . Let be an arbitrary graph with , and . Then the spectrum of is the multi-set consisting of the numbers for , each with multiplicity ; for ; multiplicity-one eigenvalues for each eigenvalue of .
Proof
By a proper labeling of the vertices and Lemma 2.1, the adjacency matrix of can be written in the following form ( stands for the all- matrix): where .
As a regular graph, has the all-one vector as an eigenvector corresponding to the eigenvalue , while all the other eigenvectors are orthogonal to . Note that as may not be connected, need not be a simple eigenvalue of . Let be an arbitrary eigenvalue of with corresponding eigenvector , such that . For each , is an eigenvector of corresponding to the eigenvalue . This is because
Let be an arbitrary eigenvalue of with corresponding eigenvector , such that . Let be an arbitrary eigenvalue of with corresponding eigenvector . By Lemma 2.2 and a similar argument we see that the vectors are eigenvectors of with corresponding eigenvalues .
In this way we obtain eigenvectors of the form , and these account for a total of eigenvectors. All these eigenvectors are orthogonal to the vectors and . This means that these vectors span the space spanned by the remaining eigenvectors of . Thus the remaining eigenvectors of are of the form for some , where and .
If is an eigenvalue of with an eigenvector , then and , . We get the system of equations: (1) (1) where .
This shows that is also an eigenvalue of the matrix since , where
Next we consider the eigenvalues of the matrix , equivalently consider the roots of , and if , (Equation1(1) (1) ) gives , since , and this in turn implies , since , a contradiction. Thus , so is nonsingular, we have Thus, the eigenvalues are obtained by solving because of , thus eigenvalues are the theorem is proved.
If we allow , the spectrum of is the spectrum of the Indu–Bala product . Then we have the following.
Corollary 3.2
For , let be an regular graph with vertices and be the eigenvalues of . Let be and . Then the spectrum of is the multi-set consisting of the numbers for , each with multiplicity ; for and four more eigenvalues are and .
Proof
By Theorem 3.1, the spectrum of is the multi-set consisting of the numbers for , each with multiplicity ; for and more eigenvalues are and , because of , the theorem is proved.
In the following, we will consider the spectrum of for regular graphs , and arbitrary graphs , in terms of their spectra.
Theorem 3.3
For , let be an regular graph with vertices and let be the eigenvalues of . Let be an arbitrary graph with , , and . Then the spectrum of is the multi-set consisting of the numbers for ; for ; and eigenvalues of a real matrix , where
Proof
By a proper labeling of the vertices and Lemma 2.1, the adjacency matrix of can be written in the form: where .
Let be an arbitrary eigenvalue of with corresponding eigenvector , such that . Let be an arbitrary eigenvalue of with corresponding eigenvector . For each and , the vectors are eigenvectors of corresponding to the eigenvalue . This is because
Similarly, let be an arbitrary eigenvalue of with corresponding eigenvector , such that . Let be an arbitrary eigenvalue of with corresponding eigenvector . By Lemma 2.2 and a similar argument we see that the vectors are eigenvectors of with corresponding eigenvalues .
In this way we obtain eigenvectors of the form , and these account for a total of eigenvectors. All these eigenvectors are orthogonal to the vectors and . This means that these vectors span the space spanned by the remaining eigenvectors of . Thus the remaining eigenvectors of are of the form for some , where and .
If is an eigenvalue of with an eigenvector , then and , . We get the system of equations: (2) (2) where and .
This shows that is also an eigenvalue of the matrix since , where
In general, it is difficult to give the explicit formula for all eigenvalues of matrix . But for , and the cases or , we have the following.
Corollary 3.4
For , let be an regular graph with vertices and let be the eigenvalues of . Let , be and . Then the spectrum of is the multi-set consisting of the numbers for ; for and four eigenvalues are and .
Proof
By Theorem 3.3, the spectrum of is the multi-set consisting of the numbers for ; for ; and four eigenvalues which are the eigenvalues of matrix and the characteristic polynomial of is , then eigenvalues are and .
Corollary 3.5
For , let be an regular graph with vertices and let be the eigenvalues of . Let , be and . Then the spectrum of is the multi-set consisting of the numbers for ; for , each with multiplicity ; for ; for each with multiplicity and six eigenvalues are , each with multiplicity and .
Proof
By Theorem 3.3, the spectrum of is the multi-set consisting of the numbers for ; for , each with multiplicity ; for ; for each with multiplicity and six eigenvalues which are the eigenvalues of matrix and the characteristic polynomial of is , then eigenvalues are and .
4 Some new integral adjacency spectrum
Which graphs have integral spectra? The number of integral graphs is not only infinite, but one can find them in all classes of graphs and among graphs of all orders. However, they are very rare and difficult to be found [Citation11].
By Corollary 3.2 computation, we have that is an integral spectrum graph. In [Citation13], Wang also shows this result.
Theorem 4.1
Let are both -regular integral graphs with vertices such that where is also a positive integer and . Then is an integral spectrum graph.
Proof
By Theorem 3.1, we mainly consider multiplicity-one eigenvalues where is an eigenvalue of . For and , then We know , when , then , each with multiplicity ; when , then or ; when , then or .
Thus, the spectrum of is where and are eigenvalues of , .
As , are both -regular integral graphs, we have that is an integral spectrum graph.
Theorem 4.2
Let be a positive integer such that where p is also a positive integer, then and are both integral spectrum graphs.
Proof
By Corollaries 3.4 and 3.5, we can obtain the spectrum of is
and the spectrum of is Hence, they are integral spectra.
Finally, the first new graph operation can also be used in constructing cospectral graphs. If and , and , and are cospectral, then and are cospectral.
Notes
Peer review under responsibility of Kalasalingam University.
This paper supported by the National Natural Science Foundation of China (No. 11571101) and the program for excellent talents in Hunan Normal University (ET13101).
References
- Cvetković D. Doob M. Sachs H. Spectra of Graphs Theory and Application third ed. 1995 Johann Ambrosius Barth Verlag
- Bondy J.A. Murty U.S.R. Graph Theory with Applications 1976 Macmillan
- Harary F. Schwenk A. Which graphs have integral spectra? Bari R. Harary F. Graphs and Combinatorics 1974 Springer-Verlag Berlin 45 51
- Bussemaker F. Cvetković D. There are exactly 13 connected cubic, integral graphs Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 544–576 1976 43 48
- Balińska K. Cvetković D. Lepović M. Simić S. There are exactly 150 connected integral graphs up to 10 vertices Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. 10 1999 95 105
- Stanić Z. There are exactly 172 connected Q-integral graphs up to 10 vertices Novi Sad J. Math. 37 2 2001 193 205
- Cvetković D. Cubic integral graphs, Univ Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 489–541 1975 107 113
- M. Lepović, S. Simić, K. Balińska, K. Zwerzyński, There are 93 non-regular, bipartite integral graphs with maximal degree four, The Techical University of Poznań,CSC Report No.511, Poznań, 2005.
- Tang Z. Hou Y. The integral graphs with index 3 and exactly two main eigenvalues Linear Algebra Appl. 433 5 2010 984 993
- Bapat R.B. Karimi M. Construction of cospectral integral regular graphs Discuss. Math. Graph Theory 37 2017 595 609
- Balińska K. Cvetković D. Radosavljević Z. Simić S. Stevanović D. A survey on integral graphs Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 13 2003 42 65
- Indulal G. Balakrishnan R. Distance spectrum of Indu-Bala product of graphs AKCE Int. J. Graphs Combin. 13 2016 230 234
- Wang L. (Ph.D. thesis) Integral Trees and Integral Graphs 2005 Univ. Twente