摘要
图论是数学重要的研究分支,在实际中有广泛的应用.图谱研究主要是用矩阵方法研究图的结构,是图论研究的热点.图谱方法已经被用来解决了许多科学难题.黄皓[Ann.Math.,2019]通过证明??维超立方体????的某种符号邻接矩阵仅有两个特征值√n和-√n,进而证明了Qn的每个含有(2n?1+1)个顶点的导出子图的最大度至少为√n,解决了困扰了计算机理论界近三十年的布尔函数灵敏度猜想.本文分别考虑了二部图Ka,b和完全图Km与Qn的符号笛卡尔积的特征值,当a=b=1或m=2时即为n+1维符号超立方体.设f(G)为G的任意含有α(G)+1个顶点的导出子图的最大度的最小值,其中α(G)为G的独立数.黄皓还提出了以下问题:一个高度对称的图,f(G)是多少?就这个问题我们研究了k元n次立方体Qkn,其中2元n次立方体就是Qn.本文通过证明Q4n某种符号邻接矩阵仅有两个符号相反的邻接特征值√2n和-√2n,从而证明Q4n的每个含有(22n?1+1)个顶点的导出子图的最大度至少为√2n,即f(Q4n)≥√2n.全文共分为五章. 第一章,绪论.介绍相关研究背景,符号图的邻接特征值的国内外研究现状,接着介绍文章的研究目的和意义,点明本文我们所要研究的方向和内容. 第二章,预备知识.定义图G=(V,E)的符号函数σ:E→{+1,?1}.简单介绍符号图Γ=(G,σ)的概念及其对应的符号邻接矩阵(0,±1)-矩阵A(Γ)=(ασij),当υi和υj相邻时,ασij=σ(υiυj),否则为0.给出最大度,两个图笛卡尔积的表示方法.给出黄皓证明敏感度猜想一文的主要内容及符号邻接矩阵的一些基本性质,包括柯西交错定理,最大度与特征值之间的关系. 第三章,符号图的笛卡尔乘积.用矩阵迭代定义相应的符号邻接矩阵.对n进行归纳用A1特征值得到An+1的特征值,包括对应重数的关系.继而我们较容易能够得到完全图Km与二部图Ka,b的邻接矩阵作为初始矩阵得到的矩阵An+1的特征值.紧接着根据最大度与符号邻接矩阵特征值的关系就可以给出完全图Km与超立方体图、二部图Ka,b与超立方体图Qn笛卡尔积所得图中任意含有一半加一个顶点的导出子图最大度的下界. 第四章,k元n次立方体图.对于黄皓提出的问题,我们研究k元n立方体图Qkn.本文利用上一章相关结论和方法,说明了只有当K≥3时只有Q4n的某种符号表示有两个符号相反的特征值,且给出了Q4n的每个含有一半加一个顶点的导出子图的最大度的下界. 第五章,总结与展望.我们对本文所研究的内容进行了总结,指出符号图特征值研究可以考虑的其他方面,包括刻画含两个特征值的符号6-正则图,对高度对称的图G考虑黄皓提出的参数f(G).
NETL