关于图谱的若干研究
|
摘要
对于一个图G,用A(G)表示图G的邻接矩阵,矩阵A(G)的特征值称为图G的特征值,图G的特征值组成的序列称为图G的谱.图的谱是图的一种重要性征,在物理和化学领域中,通过对物质分子所对应的分子图的谱的研究,可以预知该物质在某些物理和化学方面的性质.而在计算机网络中,研究网络对应的图的谱将为深入研究该网络提供一个非常有用的代数工具.但是对于大量的图来说,还不能直接求出它们的谱,因此对图的特征值的估计是图论中一个相当活跃的课题,近30年来,已有大量的文献和结果.本文主要研究了阿贝尔Cayley图,阿贝尔双Cayley图,阿贝尔混合Cayley图的谱,以及双循环有向图的一些代数性质,又刻划了一类高斯整谱循环有向图.另外,我们还研究了有向图的谱以及拟树图中Laplacian宽度最大的图等问题.
第一章,我们介绍了研究背景和一些基本概念,给出了Cayley图、双Cayley图、混合Cayley图、谱、高斯整谱图、拉普拉斯宽度等的定义.对各类研究问题的历史与现状进行了一定程度的综述.最后介绍了本文的研究内容和主要结果.第二章,我们首先研究了折叠立方体和双折叠立方体的谱；其次研究了阿贝尔Cayley图的邻接矩阵以及它的谱,由此我们给出了阿贝尔双Cayley图和混合Cayley图的谱,根据双Cayley图的定义我们又给出了有向双Cayley图的定义,进一步研究了阿贝尔群上双Cayley有向图和混合Cayley有向图的谱；最后,我们研究了有向双循环图的谱以及有向双循环图中有向支撑树个数的渐进计数定理.第三章,主要研究了二部有向图的二部补图的谱,并且定义了有向图的二部积和完全积,从而进一步研究了有向图二部积和完全积的谱.第四章,我们主要研究了拟树图的Laplacian宽度,确定了一类拟树图中Laplacian宽度最大的图是唯一的.第五章,我们主要研究了高斯整谱循环有向图,完全刻划了点数为k,2k,4k的高斯整谱循环有向图,同时给出了一类点数为2tk的高斯整谱循环有向图,其中t>2且k是奇数.
For a graph G, denote the adjacency matrix of G by A(G), the eigenvalues of A(G) are called the eigenvalues of G. The sequence of eigenvalues of G is called the spectra of graph G. The spectra of a graph is an important property of a graph. In the field of physics and chemistry, by the spectra of molecular graph, one can predict the property of this substance in physics and chemistry. And in the computer network, the spectra of the graph corresponding to the network will provide a useful algebra tool for studying this network. But for many graphs, we can not derive their spectra, thus, the estimation for the spectra of graph is an important problem in graph theory. In recent 30 years, there are many results about this problem. In this paper, we study the spectra of Cayley graphs, Bi-Cayley graphs and mixed Cayley graphs on Abelian group, give some algebraic properties of Bi-Circulant digraphs, and characterize the Gaussian integral circulant digraphs. In addition, we study the spectra of digraphs and the laplacian spread of quasi-tree graphs.
In chapter 1, we introduce the background of our study, and give the def-initions of Cayley graphs, Bi-Cayley graphs, mixed Cayley graphs, spectra of graphs, laplacian spread, etc, and the main results in this paper. In chapter 2, we firstly study the spectra of folded hypercube and Bi-folded hypercube; Secondly, we study the adjacency matrix and spectra of the Cayley graph on Abelian group, and then give the spectra of Bi-Cayley graph and mixed Cayley graph on Abelian group and the definition of the Bi-Cayley digraph, furthermore, we derive the spectra of Bi-Cayley digraph and mixed Cayley digraph on Abelian group. Finally, we investigate the spectra of Bi-Circulant digraphs and some asymptotic enumeration theorem for the number of di-rected spanning trees in Bi-Circulant digraphs are presented. In chapter 3, we consider the relation of characteristic polynomials of regular bipartite digraph D and its bipartite complement D*. Further, we define the bipartite product of bipartite graphs and derive its spectra, and then generalize the definition and results to the bipartite digraphs. In chapter 4, we study the Laplacian spread of quasi-tree graph, characterize the unique quasi-tree graph with max-imum Laplacian spread among all quasi-tree graphs in the set Q(n, d) with 1≤d≤n-4/2. In chapter 5, we completely characterize the gaussian integral circulant digraphs with order k,2k,4k, and we find a class of gaussian integral circulant digraphs with order 2tk, where t>2 and k is odd.
第一章,我们介绍了研究背景和一些基本概念,给出了Cayley图、双Cayley图、混合Cayley图、谱、高斯整谱图、拉普拉斯宽度等的定义.对各类研究问题的历史与现状进行了一定程度的综述.最后介绍了本文的研究内容和主要结果.第二章,我们首先研究了折叠立方体和双折叠立方体的谱；其次研究了阿贝尔Cayley图的邻接矩阵以及它的谱,由此我们给出了阿贝尔双Cayley图和混合Cayley图的谱,根据双Cayley图的定义我们又给出了有向双Cayley图的定义,进一步研究了阿贝尔群上双Cayley有向图和混合Cayley有向图的谱；最后,我们研究了有向双循环图的谱以及有向双循环图中有向支撑树个数的渐进计数定理.第三章,主要研究了二部有向图的二部补图的谱,并且定义了有向图的二部积和完全积,从而进一步研究了有向图二部积和完全积的谱.第四章,我们主要研究了拟树图的Laplacian宽度,确定了一类拟树图中Laplacian宽度最大的图是唯一的.第五章,我们主要研究了高斯整谱循环有向图,完全刻划了点数为k,2k,4k的高斯整谱循环有向图,同时给出了一类点数为2tk的高斯整谱循环有向图,其中t>2且k是奇数.
For a graph G, denote the adjacency matrix of G by A(G), the eigenvalues of A(G) are called the eigenvalues of G. The sequence of eigenvalues of G is called the spectra of graph G. The spectra of a graph is an important property of a graph. In the field of physics and chemistry, by the spectra of molecular graph, one can predict the property of this substance in physics and chemistry. And in the computer network, the spectra of the graph corresponding to the network will provide a useful algebra tool for studying this network. But for many graphs, we can not derive their spectra, thus, the estimation for the spectra of graph is an important problem in graph theory. In recent 30 years, there are many results about this problem. In this paper, we study the spectra of Cayley graphs, Bi-Cayley graphs and mixed Cayley graphs on Abelian group, give some algebraic properties of Bi-Circulant digraphs, and characterize the Gaussian integral circulant digraphs. In addition, we study the spectra of digraphs and the laplacian spread of quasi-tree graphs.
In chapter 1, we introduce the background of our study, and give the def-initions of Cayley graphs, Bi-Cayley graphs, mixed Cayley graphs, spectra of graphs, laplacian spread, etc, and the main results in this paper. In chapter 2, we firstly study the spectra of folded hypercube and Bi-folded hypercube; Secondly, we study the adjacency matrix and spectra of the Cayley graph on Abelian group, and then give the spectra of Bi-Cayley graph and mixed Cayley graph on Abelian group and the definition of the Bi-Cayley digraph, furthermore, we derive the spectra of Bi-Cayley digraph and mixed Cayley digraph on Abelian group. Finally, we investigate the spectra of Bi-Circulant digraphs and some asymptotic enumeration theorem for the number of di-rected spanning trees in Bi-Circulant digraphs are presented. In chapter 3, we consider the relation of characteristic polynomials of regular bipartite digraph D and its bipartite complement D*. Further, we define the bipartite product of bipartite graphs and derive its spectra, and then generalize the definition and results to the bipartite digraphs. In chapter 4, we study the Laplacian spread of quasi-tree graph, characterize the unique quasi-tree graph with max-imum Laplacian spread among all quasi-tree graphs in the set Q(n, d) with 1≤d≤n-4/2. In chapter 5, we completely characterize the gaussian integral circulant digraphs with order k,2k,4k, and we find a class of gaussian integral circulant digraphs with order 2tk, where t>2 and k is odd.
引文
[1]N.L. Biggs, Algebraic Graph Theory [M], second ed., Cambridge University Press, Cambridge,1993.
[2]D.M. Cvetkovi'c, M. Doob, H. Sachs, Spectra of Graphs [M], Theory and Applica-tions, second ed., Deutscher Verlag der Wissenschaften, Berlin,1982.
[3]D.M. Cvetkovic, The Boolean operations on graphs-spectrum and connectedness [J]. Booleove operacije nad grafovima-spektar i povezanost (summary).V. Kongres mat., fiz. iastr. na Jugoslavija, Ohrid 1970; Zbornik na trudovite, tom I, Skopje 1973; 115-119.
[4]S.M. Cioaba, Closed walks and eigenvalues of Abelian Cayley graphs [J], C.R.Acad.Sci.Paris, Ser.I 342(2006)635-638.
[5]C. Godsil, G. Royle, Algebraic Graph Theory [M], Springer-Verlag New York, Inc,2001.
[6]T.A. Horn, C.R. Johnson, Matrix analysis [M], Cambridge:Cambridge University Press,1985.
[7]J.L. Alperin, R.B. Bell, Groups and Representations [M], Springer-Verlag New York, 1997.
[8]F. Chung, Spectral Graph Theory [M], American Mathematical Society, Providence, RI,1997.
[9]F. Comellas, M.A. Fiol, J. Gimbert, M. Mitjana, The spectra of wrapped butterfly graphs [J], Networks 42(2003),15-19.
[10]F. Comellas, M.A. Fiol, J. Gimbert, M. Mitjana, The spectra of Manhattan street networks [J], Linear Algebra Appl.429(2008),1823-1839.
[11]C. Eschenbach, F. Hall, R. Hemasinha, S.J. Kirkland, Z. Li, B.L. Shader, J.L. Stu-art, J.R. Weaver, On almost regular tournament matrices [J], Linear Algebra Appl. 306(2000)103-121.
[12]A. Mowshowitz, The characteristic polynomial of a graph [J], J.Combin.Thwory, Ser.B 12 (1972)177-193.
[13]J. Snellman, The Maximal spectral radius of a digraph with (M+1)2-S edges [J], Electron. J.Linear Algebra 10 (2003)179-189.
[14]G,H. Xu,C.Q. Xu, Sharp bound for the spectral radius of digraphs [J], linear Algebra Appl,430(2009) 1607-1612.
[15]M. Devos, L. Goddyn, B. Mohar, R. Samal, Cayley sum graphs and eigenvalues of (3,6)-fullerenes [J], J. Combin. Theory Ser. B (2008), doi:10.1016/j.jctb.2008.08.005.
[16]Y. Hong, J.L. Shu, Sharp lower bounds of the least eigenvalue of planar graphs [J], Linear Algebra and its Applications 296(1999)227-232.
[17]M. Lu, H.Q. Liu, F. Tian, Bounds of Laplacian spectrum of graphs based on the domination number [J], Linear Algebra and its Applications 402(2005)390-396.
[18]H.Q. Liu, M. Lu, F. Tian, On the Laplacian spectral radius of a graph [J], Linear Algebra and its Applications 376(2004)135-141.
[19]H.Q. Liu, M. Lu, F. Tian,On the spectral radius of graphs with cut edges [J], Linear Algebra and its Applications 389(2004)139-145.
[20]H.Q. Liu, M. Lu, F. Tian,On the spectral radius of unicyclic graphs with fixed di-ameter [J], Linear Algebra and its Applications 420(2007)449-457.
[21]J.L. Shu, Y. Hong, K.W. Ren, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph [J], Linear Algebra and its Applications 347(2002)123-
[22]B.F. Wu, E.L. Xiao, Yuan Hong, The spectral radius of trees on k pendant vertices [J], Linear Algebra and its Applications 395(2005)343-349.
[23]A.M. Yu, M. Lu, F. Tian, On the spectral radius of graphs [J], Linear Algebra and its Applications 387(2004)41-49.
[24]L. Babai, Spectra of Cayley graph [J], J.Combin.Theory Ser.B,27(1979),180-189.
[25]J.Y. Chen, J.X. Meng, L.H. Huang, Supper edge-connectivity of mixed Cayley graph [J], Discrete Mathematics,309(2009),264-270.
[26]I. Kovas, A. Malnic, D. Marusic, S. Miklavic, One-matching bi-Cayley graphs over abelian groups [J], European Journal of Combinatorics (2008), doi:10.1016/j. ejc. 2008.06.001.
[27]L. Lovasz, Spectra of graphs with transitive groups [J], Period. Math. Hungar. 6(1975),191-196.
[28]M.Y. Xu, Introduction of finite groups Ⅱ[M], Beijing:Science Press,1999(in Chinese).
[29]H. Zou, J.X. Meng, Some algebraic properties of Bi-Cayley Graphs [J], Acta Math-ematica Sinica, Chinese Series 50 (5) (2007) 1075-1080.
[30]J. Friedman, R. Murty, J.P. Tillich, Spectral estimates for Abelian Cayley graphs [J], Journal of Combinatorial Theory, Series B 96 (2006) 111-121.
[31]M.A. Thornton, Mixed-radix MVL Function Spectral and Decision Diagram Repre-sentation [J], Automation and Rernote Control, Vol.65, No.6,2004, pp.1007-1017.
[32]Y. Kohayakawa, V. Rodl, M. Schacht, Discrepancy and eigenvalues of Cayley graphs [J],1991 Mathematics Subject Classification. Primary:05C50. Secondary:05C80.
[33]M.Y. Xu, Automorphism of Groups and Isomorphisms of Cayley Digraphs [J], Dis-crete Mathematics 182(1998),309-319.
[34]W. So, Integral circulant graphs [J], Discrete Mathematics 306(2005),153-158.
[35]J.M. Xu, Topological Structure and Analysis of Interconnection Networks [J], Kluwer Academic Publishers, (2001).
[36]J. Xu, R.B. Qu, The spectra of Hypercubes [J], Journal of Engneering Mathematics, 4(1999),1-5.
[37]T. Atajan, X.R. Yong, H. Inaba, Further nanlysis of the number of spanning trees in circulant graphs [J], Discrete Mathematic 306 (2006),2817-2827.
[38]T. Atajan, X.R. Yong, The number of spanning trees of three special cycles [J], in: Proceedings of Zheng Zhou Conference on Computing, China,1994.
[39]G. Baron, H. Prodinger, R.F. Tichy, F.T. Boesch, J.F. Wang, The number of span-ning trees in the square of a cycle [J], Fibonacci Quart.23.3 (1985),258-264.
[40]S. Bedrosian, The Fibonacci numbers via trigonometric expressions [J], J. Franklin Inst.295 (1973),175-177.
[41]J.C. Bermond, F. Comellas, D.F. Hsu, Distributed loop computer networks:a survey [J], J.Parallel Distribution Comput.24(1995),2～10.
[42]F.T. Boesch, H. Prodinger, Spanning tree formulas and Chebyshev polynomials [J], Graphs Combin.2(1986),191-200.
[43]F.T. Boesch, J.F. Wang, A conjecture on the number of spanning trees in the square of a cycle [J], in:Notes from New York Graph Theory Day V, New York Academy Sciences, New York,1982, p.16.
[44]G. Kirchhok, U ber die Au osung der Gleichungen, auf welche man bei der Unter-suchung der linearen Verteilung galvanischer Strome gefuhrt wird [J], Ann. Phys. Chem.72 (1847) 497-508.
[45]D.J. Kleitman, B. Golden, Counting trees in a certain class of graphs [J], Amer. Math. Mon.82 (1975) 40-44.
[46]X.B. Chen, Q.Y. Lin, F.J. Zhang, The number of spanning trees in odd valent cir-culant graphs [J], Discrete Mathematic 282 (2004) 69-79.
[47]X.B. Chen, The number of spanning trees in directed circulant graphs with non-fixed jumps [J], Discrete Mathematics 306 (2007) 1873-1880.
[48]X.B. Chen, The numbers of spanning trees in undirected circulant graphs [J], J. Zhangzhou Teachers Coll,13(4) (2000),1-6.
[49]X.R. Yong, F.J. Zhang, An asymptotic property of the number of spanning trees of double fixed step loop networks[J], Appl.Math.-JCU, Ser.B 12(1997) 233-236.
[50]X.R:Yong, T. Acenjian, The numbers of spanning trees of the cycle CN3 and the quadrupe cycle CN4[J], Discrete Math.169(1997),293-298.
[51]F.J. Zhang, X.Y. Yong, Asymptotic enumeration theorem for the number of spanning trees and Eulerian trails in circulant digraphs and graphs [J], Sci.China, Ser A 43 (2) (1999) 264-271.
[52]F.J. Zhang, G.N. Lin, The complixity of digraphs [J], In:Capobianco MF.Guan M.Hsu DF,eds.Graphs Theory and Its Aplication East and West (1989) 171-180.
[53]Y.P. Zhang, X.R. Yong, M.J. Golin, The number of spanning trees in circulant graphs [J], Discrete Mathematic 223 (2000) 337-350.
[54]R. Brualdi, Spectra of digraphs [J], Linear Algebra Appl. (2009), doi:10.1016/j. laa. 2009.02.033.
[55]J. Bang, G. Gutin, Digraphs:Theory, Algorithms and Applications [M], Springer 2002.
[56]D.M. Cvetkovi'c, Graphs and their spectra [J].(Thesis). Univ. Beograd Publ. Elek-trotehn. Fak., Ser. Mat. Fiz., No.354-No.356(1971),1-50.
[57]F. Esser, F. Harary, Digraphs with real and gaussian spectra [J], Discrete Applied Mathematics 2 (1980)113-124.
[58]F. Harary, C. King, A. Mowshowitz, R.C. Read. Cospectral graphs and digraphs [J], Bull.London Math.Soc.3(1971)321-328.
[59]M.H. Mcandrew, On the product of directed graphs [J], Proc. Amer. Math. Soc. 14(1963)600-606.
[60]A.J.Schwenk, Computing the characteristic polynomial of a graph [J]. in:R.Bari and F.Harary, eds. Springer Lecture Notes 406 (1974)153-172.
[61]Y. Teranishi, Equitable switching and spectra of graphs [J], Linear Algebra and its Application 359(2003)121-131.
[62]Y. Teranishi, F.Yasuno, The second largest eigenvalues of regular bipartite graphs [J], Kyushu J. Math.54 (2000) 39-54.
[63]Y.S. Zhou, T.F. Li, Some algebraic properties of the digraph [J], Journal of Jinan University. (Natural Science),22(1982),22-26.
[64]C.D. Godsil,Eigenvalues of graphs and digraphs [J], Linear Algebra Appl.46 (1982)43-50.
[65]C.D. Godsil,B. Mckay,Products of graphs and their spectra [J], in Combinarotial Mathematics IV, Lecture Note in Mathematics, vol.560, Springer,Belin,1977,pp.91-117.
[66]J. Kwapisz, On the spectral radius of a directed graph [J], J.Graph.Theory 23 (1996)405-411.
[67]G. Lin, F. Zhang, On the charecteristic polynomial of directed line graph and a type of cospectral directed graph [J], KexueTongBao(Chinese)22 (1983)348-350.
[68]W:N. Anderson,T.D. Morely, Eigenvalues of the Laplacian of a graph [J], Linear Multilinear Algebra 18(1985),141-145.
[69]Y.H. Bao, Y.Y. Tan,Y.Z. Fan, The Laplacian spread of unicyclic graphs [J], Applied Mathematics Letters 22(2009),1011-1015.
[70]Y. Chen, L. Wang, The Laplacian spread of tricyclic graphs [J], The Electronic Journal of Combinatoric 16 (2009),1-18.
[71]K. Das, An improved upper bound for Laplacian graph eigenvalues [J], Linear Algebra Appl.368(2003),269-278.
[72]M. Fiedler, Algebraic connectivity:of graphs[J], Czechoslovak Math:J.23(1973); 298-305.
[73]Y.Z. Fan, Y. Wang, Y.B. Gao, Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread [J], Linear Algebra Appl.429(2-3) (2008),577-588.
[74]Y.Z. Fan, J. Xu, Y. Wang, D. Liang, The Laplacian spread, of a tree [J]., Discrete Math. Theor. Comput.Sci.10(1)(2008),79-86.
[75]Y.Z. Fan, S.D. Li, Y.Y. Tan, The Laplacian spread of bicyclic graphs [J], Journal of Mathematical Research & Exposition,30(1) (2010),17-28.
[76]D. Gregory, D. Hershkowitz, S. Kirkland, The spread of the spectrum of a graph [J], Linear Algebra Appl.332-334(2001),23-35.
[77]R. Grone, R. Merris, The Laplacian spectrum of a graph II [J],SIAM J.Discrete Math.7(1994),229-237.
[78]C.R. Johnson, R. Kumar, H. Wolkowicz, Lower bounds for the spread of a matrix [J], Linear Algebra Appl.77(1985),161-173.
[79]S. Kirkland, A bound on the algebraic connectivity of a graph in terms of the number of cutpoints [J], Linear Multilinear Algebra 47(2000),93-103.
[80]X. Li, J. Zhang, B. Zhou, The spread of unicyclic graphs with given size of maximum matchings [J], J.Math.Chem.42(4)(2007),775-788.
[81]B.L. Liu, M.H. Liu, On the spread of the spectrum of a graph [J], Discrete Mathe-matics309(2009),2727-2732.
[82]H.Q. Liu, M. Lu, On the spectral radius of quasi-tree graphs [J], Linear Algebra Appl.428(2008),2708-2714.
[83]L. Mirsky, The spread of a matrix [J], Mathematika 3 (1956),127-130.
[84]R. Merris, Laplacian matrices of graphs:A survey [J], Linear Algebra Appl.197-198(1998),143-176.
[85]R. Merris, A note on Laplacian graph eigenvalue [J], Linear Algebra Appl.285(1998), 33-35.
[86]B. Mohar, Some applications of Laplacian eigenvalues of graphs [J], in:G. Hahn,G.Sabidussi (Eds.), Graph Symmetry, Kluwer Academic Publishers, Dordrecht,1997, pp.225-275.
[87]P. Nylen, T. Y. Tam, On the spread of a Hermitian matrix and a conjecture of Thomp-son [J], Linear Multilinear Algebra 37 (1994),3-11.
[88]V. Nikiforov, Linear combinations of graph eigenvlues [J], Electron.J.Linear Algebra 15(2006),329-336.
[89]M. Petrovic, On graph whose spectral spread does not exceed 4 [J], Publ. Inst. Mat. 34(48)(1983),169-174.
[90]Z.F. You, B.L. Liu, The minimum Laplacian spread of unicyclic grpahs [J], Linear Algebra and its Applications (2009), doi:10.1016/j. laa.2009.08.027.
[91]K. Balinska, D. Cvetkovic, Z. Radosavljevic, S. Simic, D. Stevanovic, A Survey on Integral Graphs [J], Univ. Beograd. Publ. Elektrotehn.Fak. Ser. Mat.13(2002),42-65..
[92]F. Esser, F. Harary, Digraphs with real and Gaussian spectra [J], Discrete Applied Math.,2(1980),113-124.
[93]F.C. Bussemaker, D. Cvetkovic, There are exactly 13 connected, cubic, integral graphs [J], Univ.Beograd, Pub. Elektrotehn. Fak. Ser. Mat. Fiz.544(1976) 43-48.
[94]K.Q. Feng, Introduction of algebraic number theory [M], Shanghai science publica-tion,1988.
[95]X.L. Li, G.N. Lin, On integral trees problems [J], KeXue TongBao,33(1988),802-806.
[96]L.C. washington, Introduction to Cyclotomic Fields (Second Edition) [M], Springer-Verlag New York, Inc,2003.
[97]W. So, Integral circulant graphs [J], Discrete Mathematics,306(2005),153-158.
[98]H.R. Zhang, Constructing Integral Directed Graph by Circulant Matrix Methods [J], J.of Zhengzhou Univ,Vol.37 No4(2005),28-34.
[99]D. Cvetkovic, S. Simic, D. Stevanovic,4-regular integral graphs [J], Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat.,9(1998),89-102.
[2]D.M. Cvetkovi'c, M. Doob, H. Sachs, Spectra of Graphs [M], Theory and Applica-tions, second ed., Deutscher Verlag der Wissenschaften, Berlin,1982.
[3]D.M. Cvetkovic, The Boolean operations on graphs-spectrum and connectedness [J]. Booleove operacije nad grafovima-spektar i povezanost (summary).V. Kongres mat., fiz. iastr. na Jugoslavija, Ohrid 1970; Zbornik na trudovite, tom I, Skopje 1973; 115-119.
[4]S.M. Cioaba, Closed walks and eigenvalues of Abelian Cayley graphs [J], C.R.Acad.Sci.Paris, Ser.I 342(2006)635-638.
[5]C. Godsil, G. Royle, Algebraic Graph Theory [M], Springer-Verlag New York, Inc,2001.
[6]T.A. Horn, C.R. Johnson, Matrix analysis [M], Cambridge:Cambridge University Press,1985.
[7]J.L. Alperin, R.B. Bell, Groups and Representations [M], Springer-Verlag New York, 1997.
[8]F. Chung, Spectral Graph Theory [M], American Mathematical Society, Providence, RI,1997.
[9]F. Comellas, M.A. Fiol, J. Gimbert, M. Mitjana, The spectra of wrapped butterfly graphs [J], Networks 42(2003),15-19.
[10]F. Comellas, M.A. Fiol, J. Gimbert, M. Mitjana, The spectra of Manhattan street networks [J], Linear Algebra Appl.429(2008),1823-1839.
[11]C. Eschenbach, F. Hall, R. Hemasinha, S.J. Kirkland, Z. Li, B.L. Shader, J.L. Stu-art, J.R. Weaver, On almost regular tournament matrices [J], Linear Algebra Appl. 306(2000)103-121.
[12]A. Mowshowitz, The characteristic polynomial of a graph [J], J.Combin.Thwory, Ser.B 12 (1972)177-193.
[13]J. Snellman, The Maximal spectral radius of a digraph with (M+1)2-S edges [J], Electron. J.Linear Algebra 10 (2003)179-189.
[14]G,H. Xu,C.Q. Xu, Sharp bound for the spectral radius of digraphs [J], linear Algebra Appl,430(2009) 1607-1612.
[15]M. Devos, L. Goddyn, B. Mohar, R. Samal, Cayley sum graphs and eigenvalues of (3,6)-fullerenes [J], J. Combin. Theory Ser. B (2008), doi:10.1016/j.jctb.2008.08.005.
[16]Y. Hong, J.L. Shu, Sharp lower bounds of the least eigenvalue of planar graphs [J], Linear Algebra and its Applications 296(1999)227-232.
[17]M. Lu, H.Q. Liu, F. Tian, Bounds of Laplacian spectrum of graphs based on the domination number [J], Linear Algebra and its Applications 402(2005)390-396.
[18]H.Q. Liu, M. Lu, F. Tian, On the Laplacian spectral radius of a graph [J], Linear Algebra and its Applications 376(2004)135-141.
[19]H.Q. Liu, M. Lu, F. Tian,On the spectral radius of graphs with cut edges [J], Linear Algebra and its Applications 389(2004)139-145.
[20]H.Q. Liu, M. Lu, F. Tian,On the spectral radius of unicyclic graphs with fixed di-ameter [J], Linear Algebra and its Applications 420(2007)449-457.
[21]J.L. Shu, Y. Hong, K.W. Ren, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph [J], Linear Algebra and its Applications 347(2002)123-
[22]B.F. Wu, E.L. Xiao, Yuan Hong, The spectral radius of trees on k pendant vertices [J], Linear Algebra and its Applications 395(2005)343-349.
[23]A.M. Yu, M. Lu, F. Tian, On the spectral radius of graphs [J], Linear Algebra and its Applications 387(2004)41-49.
[24]L. Babai, Spectra of Cayley graph [J], J.Combin.Theory Ser.B,27(1979),180-189.
[25]J.Y. Chen, J.X. Meng, L.H. Huang, Supper edge-connectivity of mixed Cayley graph [J], Discrete Mathematics,309(2009),264-270.
[26]I. Kovas, A. Malnic, D. Marusic, S. Miklavic, One-matching bi-Cayley graphs over abelian groups [J], European Journal of Combinatorics (2008), doi:10.1016/j. ejc. 2008.06.001.
[27]L. Lovasz, Spectra of graphs with transitive groups [J], Period. Math. Hungar. 6(1975),191-196.
[28]M.Y. Xu, Introduction of finite groups Ⅱ[M], Beijing:Science Press,1999(in Chinese).
[29]H. Zou, J.X. Meng, Some algebraic properties of Bi-Cayley Graphs [J], Acta Math-ematica Sinica, Chinese Series 50 (5) (2007) 1075-1080.
[30]J. Friedman, R. Murty, J.P. Tillich, Spectral estimates for Abelian Cayley graphs [J], Journal of Combinatorial Theory, Series B 96 (2006) 111-121.
[31]M.A. Thornton, Mixed-radix MVL Function Spectral and Decision Diagram Repre-sentation [J], Automation and Rernote Control, Vol.65, No.6,2004, pp.1007-1017.
[32]Y. Kohayakawa, V. Rodl, M. Schacht, Discrepancy and eigenvalues of Cayley graphs [J],1991 Mathematics Subject Classification. Primary:05C50. Secondary:05C80.
[33]M.Y. Xu, Automorphism of Groups and Isomorphisms of Cayley Digraphs [J], Dis-crete Mathematics 182(1998),309-319.
[34]W. So, Integral circulant graphs [J], Discrete Mathematics 306(2005),153-158.
[35]J.M. Xu, Topological Structure and Analysis of Interconnection Networks [J], Kluwer Academic Publishers, (2001).
[36]J. Xu, R.B. Qu, The spectra of Hypercubes [J], Journal of Engneering Mathematics, 4(1999),1-5.
[37]T. Atajan, X.R. Yong, H. Inaba, Further nanlysis of the number of spanning trees in circulant graphs [J], Discrete Mathematic 306 (2006),2817-2827.
[38]T. Atajan, X.R. Yong, The number of spanning trees of three special cycles [J], in: Proceedings of Zheng Zhou Conference on Computing, China,1994.
[39]G. Baron, H. Prodinger, R.F. Tichy, F.T. Boesch, J.F. Wang, The number of span-ning trees in the square of a cycle [J], Fibonacci Quart.23.3 (1985),258-264.
[40]S. Bedrosian, The Fibonacci numbers via trigonometric expressions [J], J. Franklin Inst.295 (1973),175-177.
[41]J.C. Bermond, F. Comellas, D.F. Hsu, Distributed loop computer networks:a survey [J], J.Parallel Distribution Comput.24(1995),2～10.
[42]F.T. Boesch, H. Prodinger, Spanning tree formulas and Chebyshev polynomials [J], Graphs Combin.2(1986),191-200.
[43]F.T. Boesch, J.F. Wang, A conjecture on the number of spanning trees in the square of a cycle [J], in:Notes from New York Graph Theory Day V, New York Academy Sciences, New York,1982, p.16.
[44]G. Kirchhok, U ber die Au osung der Gleichungen, auf welche man bei der Unter-suchung der linearen Verteilung galvanischer Strome gefuhrt wird [J], Ann. Phys. Chem.72 (1847) 497-508.
[45]D.J. Kleitman, B. Golden, Counting trees in a certain class of graphs [J], Amer. Math. Mon.82 (1975) 40-44.
[46]X.B. Chen, Q.Y. Lin, F.J. Zhang, The number of spanning trees in odd valent cir-culant graphs [J], Discrete Mathematic 282 (2004) 69-79.
[47]X.B. Chen, The number of spanning trees in directed circulant graphs with non-fixed jumps [J], Discrete Mathematics 306 (2007) 1873-1880.
[48]X.B. Chen, The numbers of spanning trees in undirected circulant graphs [J], J. Zhangzhou Teachers Coll,13(4) (2000),1-6.
[49]X.R. Yong, F.J. Zhang, An asymptotic property of the number of spanning trees of double fixed step loop networks[J], Appl.Math.-JCU, Ser.B 12(1997) 233-236.
[50]X.R:Yong, T. Acenjian, The numbers of spanning trees of the cycle CN3 and the quadrupe cycle CN4[J], Discrete Math.169(1997),293-298.
[51]F.J. Zhang, X.Y. Yong, Asymptotic enumeration theorem for the number of spanning trees and Eulerian trails in circulant digraphs and graphs [J], Sci.China, Ser A 43 (2) (1999) 264-271.
[52]F.J. Zhang, G.N. Lin, The complixity of digraphs [J], In:Capobianco MF.Guan M.Hsu DF,eds.Graphs Theory and Its Aplication East and West (1989) 171-180.
[53]Y.P. Zhang, X.R. Yong, M.J. Golin, The number of spanning trees in circulant graphs [J], Discrete Mathematic 223 (2000) 337-350.
[54]R. Brualdi, Spectra of digraphs [J], Linear Algebra Appl. (2009), doi:10.1016/j. laa. 2009.02.033.
[55]J. Bang, G. Gutin, Digraphs:Theory, Algorithms and Applications [M], Springer 2002.
[56]D.M. Cvetkovi'c, Graphs and their spectra [J].(Thesis). Univ. Beograd Publ. Elek-trotehn. Fak., Ser. Mat. Fiz., No.354-No.356(1971),1-50.
[57]F. Esser, F. Harary, Digraphs with real and gaussian spectra [J], Discrete Applied Mathematics 2 (1980)113-124.
[58]F. Harary, C. King, A. Mowshowitz, R.C. Read. Cospectral graphs and digraphs [J], Bull.London Math.Soc.3(1971)321-328.
[59]M.H. Mcandrew, On the product of directed graphs [J], Proc. Amer. Math. Soc. 14(1963)600-606.
[60]A.J.Schwenk, Computing the characteristic polynomial of a graph [J]. in:R.Bari and F.Harary, eds. Springer Lecture Notes 406 (1974)153-172.
[61]Y. Teranishi, Equitable switching and spectra of graphs [J], Linear Algebra and its Application 359(2003)121-131.
[62]Y. Teranishi, F.Yasuno, The second largest eigenvalues of regular bipartite graphs [J], Kyushu J. Math.54 (2000) 39-54.
[63]Y.S. Zhou, T.F. Li, Some algebraic properties of the digraph [J], Journal of Jinan University. (Natural Science),22(1982),22-26.
[64]C.D. Godsil,Eigenvalues of graphs and digraphs [J], Linear Algebra Appl.46 (1982)43-50.
[65]C.D. Godsil,B. Mckay,Products of graphs and their spectra [J], in Combinarotial Mathematics IV, Lecture Note in Mathematics, vol.560, Springer,Belin,1977,pp.91-117.
[66]J. Kwapisz, On the spectral radius of a directed graph [J], J.Graph.Theory 23 (1996)405-411.
[67]G. Lin, F. Zhang, On the charecteristic polynomial of directed line graph and a type of cospectral directed graph [J], KexueTongBao(Chinese)22 (1983)348-350.
[68]W:N. Anderson,T.D. Morely, Eigenvalues of the Laplacian of a graph [J], Linear Multilinear Algebra 18(1985),141-145.
[69]Y.H. Bao, Y.Y. Tan,Y.Z. Fan, The Laplacian spread of unicyclic graphs [J], Applied Mathematics Letters 22(2009),1011-1015.
[70]Y. Chen, L. Wang, The Laplacian spread of tricyclic graphs [J], The Electronic Journal of Combinatoric 16 (2009),1-18.
[71]K. Das, An improved upper bound for Laplacian graph eigenvalues [J], Linear Algebra Appl.368(2003),269-278.
[72]M. Fiedler, Algebraic connectivity:of graphs[J], Czechoslovak Math:J.23(1973); 298-305.
[73]Y.Z. Fan, Y. Wang, Y.B. Gao, Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread [J], Linear Algebra Appl.429(2-3) (2008),577-588.
[74]Y.Z. Fan, J. Xu, Y. Wang, D. Liang, The Laplacian spread, of a tree [J]., Discrete Math. Theor. Comput.Sci.10(1)(2008),79-86.
[75]Y.Z. Fan, S.D. Li, Y.Y. Tan, The Laplacian spread of bicyclic graphs [J], Journal of Mathematical Research & Exposition,30(1) (2010),17-28.
[76]D. Gregory, D. Hershkowitz, S. Kirkland, The spread of the spectrum of a graph [J], Linear Algebra Appl.332-334(2001),23-35.
[77]R. Grone, R. Merris, The Laplacian spectrum of a graph II [J],SIAM J.Discrete Math.7(1994),229-237.
[78]C.R. Johnson, R. Kumar, H. Wolkowicz, Lower bounds for the spread of a matrix [J], Linear Algebra Appl.77(1985),161-173.
[79]S. Kirkland, A bound on the algebraic connectivity of a graph in terms of the number of cutpoints [J], Linear Multilinear Algebra 47(2000),93-103.
[80]X. Li, J. Zhang, B. Zhou, The spread of unicyclic graphs with given size of maximum matchings [J], J.Math.Chem.42(4)(2007),775-788.
[81]B.L. Liu, M.H. Liu, On the spread of the spectrum of a graph [J], Discrete Mathe-matics309(2009),2727-2732.
[82]H.Q. Liu, M. Lu, On the spectral radius of quasi-tree graphs [J], Linear Algebra Appl.428(2008),2708-2714.
[83]L. Mirsky, The spread of a matrix [J], Mathematika 3 (1956),127-130.
[84]R. Merris, Laplacian matrices of graphs:A survey [J], Linear Algebra Appl.197-198(1998),143-176.
[85]R. Merris, A note on Laplacian graph eigenvalue [J], Linear Algebra Appl.285(1998), 33-35.
[86]B. Mohar, Some applications of Laplacian eigenvalues of graphs [J], in:G. Hahn,G.Sabidussi (Eds.), Graph Symmetry, Kluwer Academic Publishers, Dordrecht,1997, pp.225-275.
[87]P. Nylen, T. Y. Tam, On the spread of a Hermitian matrix and a conjecture of Thomp-son [J], Linear Multilinear Algebra 37 (1994),3-11.
[88]V. Nikiforov, Linear combinations of graph eigenvlues [J], Electron.J.Linear Algebra 15(2006),329-336.
[89]M. Petrovic, On graph whose spectral spread does not exceed 4 [J], Publ. Inst. Mat. 34(48)(1983),169-174.
[90]Z.F. You, B.L. Liu, The minimum Laplacian spread of unicyclic grpahs [J], Linear Algebra and its Applications (2009), doi:10.1016/j. laa.2009.08.027.
[91]K. Balinska, D. Cvetkovic, Z. Radosavljevic, S. Simic, D. Stevanovic, A Survey on Integral Graphs [J], Univ. Beograd. Publ. Elektrotehn.Fak. Ser. Mat.13(2002),42-65..
[92]F. Esser, F. Harary, Digraphs with real and Gaussian spectra [J], Discrete Applied Math.,2(1980),113-124.
[93]F.C. Bussemaker, D. Cvetkovic, There are exactly 13 connected, cubic, integral graphs [J], Univ.Beograd, Pub. Elektrotehn. Fak. Ser. Mat. Fiz.544(1976) 43-48.
[94]K.Q. Feng, Introduction of algebraic number theory [M], Shanghai science publica-tion,1988.
[95]X.L. Li, G.N. Lin, On integral trees problems [J], KeXue TongBao,33(1988),802-806.
[96]L.C. washington, Introduction to Cyclotomic Fields (Second Edition) [M], Springer-Verlag New York, Inc,2003.
[97]W. So, Integral circulant graphs [J], Discrete Mathematics,306(2005),153-158.
[98]H.R. Zhang, Constructing Integral Directed Graph by Circulant Matrix Methods [J], J.of Zhengzhou Univ,Vol.37 No4(2005),28-34.
[99]D. Cvetkovic, S. Simic, D. Stevanovic,4-regular integral graphs [J], Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat.,9(1998),89-102.