论文部分内容阅读
代数图论是图论的重要研究领域之一,主要运用代数方法来解决图论问题.代数图论有三个主要分支,分别为图与线性代数、图与群论、图不变量,其中第一个分支主要研究图的谱理论,第二个分支主要研究具有某种特定对称性的图,第三个分支主要研究图不变量的代数性质.凯莱图(Cayley graph),作为一类对称性较好的图,是代数图论前两个分支的重要研究对象.特别地,研究凯莱图的邻接谱间隔(adjacency spectral gap)、同构分类及自同构群等具有重要理论意义和应用价值.不同特征值数目较少的图通常也具有高度的对称性,其刻画问题近二十年也受到较多的关注.基于这些,本文研究了与凯莱图的邻接谱间隔、同构分类与计数、自同构群相关的若干问题以及不同特征值数目较少的图的刻画问题.本文分为五章,具体结构如下:第一章首先介绍了代数图论的研究背景,其次给出了本文所用到的基本概念与符号,接着概述了本文所涉及问题的研究进展,最后介绍了本文的主要结果.第二章研究了凯莱图的邻接谱间隔.首先证明了凯莱图的不属于某个特殊等价划分商矩阵的特征值可以被其某些子图的第二大特征值之和界定;其次将证明一个连通(共轭)正规凯莱图的第二大特征值等于其特定等价划分商矩阵第二大特征值的问题归结为对一些阶数比较小的图来验证结论,最后确定了对称群Sn上满足m = maxτ∈T |supp(τ)| ≤ 4的大部分连通(共轭)正规凯莱图G = Cay(Sn,T)(以及这些图的一些子图)的邻接谱间隔,并给出了这些图的等周数的下界.第三章研究了二面体群D2p(p是奇素数)上凯莱图的同构分类及计数.首先利用图谱方法确定了 D2p上三正则凯莱图的所有同构类(该结果印证了D2p是CI-群这一结论),并证明了 D2p上的所有三正则凯莱图都是Cay-DS图;其次利用高斯二次互反律给出了 D2p上三正则凯莱图同构类的数目;最后利用D2p是DCI-群这一事实及波利亚计数定理,给出了同构意义下D2p上所有(有向)凯莱图的数目,特别还确定了同构意义下D2p上出度为k的有向凯莱图的数目.第四章研究了交错群An和对称群Sn上凯莱图的自同构群.首先证明了完全交错群图CAGn=Cay(An,S)(其中S是由Sn中的所有3-轮换构成的集合,n ≥ 4)不是正规凯莱图;其次借助于分析CAGn的局部结构及考虑其自同构群阶数的上界,确定了CAGn的自同构群;最后还确定了Sn上一类三正则凯莱图的自同构群.第五章研究了不同特征值数目较少的图的刻画问题.首先刻画了含有特征值-1(或0)的恰有四个不同(邻接)特征值且其中两个是单特征值的连通正则图,并证明了这类图是邻接谱确定的;其次刻画了恰有三个不同正规化拉普拉斯特征值且其中一个是1的连通图,并借助于阿达马设计确定了恰有四个不同正规化拉普拉斯特征值的带有悬挂点的连通二部图;最后刻画了第三大距离特征值不超过-1且第二小距离特征值不小于-2的连通图,并确定了至多有三个距离特征值不同于-1和-2的所有连通图.