【作者】 许英；

【导师】 孟吉翔；

【作者基本信息】 新疆大学 ， 应用数学， 2010， 博士

【摘要】 对于一个图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是奇数.更多还原

【Abstract】 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.更多还原