关键词:
二部图
因子
边数
邻接矩阵
特征值
结合数
韧度
摘要:
极值图论是现代图论的一个重要分支,主要研究图中存在(或禁用)某些特型子结构时,图参数(如边数、最小度、连通度、结合数、韧度等)的最大值或最小值,并刻画达到这些极值的极图结构.图谱理论是图论中另一个活跃且重要的研究领域,其核心是通过图的相关矩阵的代数性质来刻画图的结构特征.作为图谱理论和极值图论的交叉研究内容,谱极值图论主要研究与图相关的各种矩阵的谱性质,特别是研究给定顶点数并且不含有特型子结构的图集中图的谱半径或其他特征值的最大值或最小值,并刻画对应的极图.
因子理论也是图论的一个重要分支,主要研究图中满足特定条件的子图,这些子图被称为因子.具体来说,因子是图中满足某些预定义的度约束或其他性质的生成子图.因子理论的核心问题是研究图中是否存在某种特定类型的因子,以及如何构造或分解这些因子.
本学位论文立足于图的谱理论与结构理论,以二部图为研究对象,主要研究不含某些特型因子的二部图的极值问题,以及二部图的结构参数与邻接谱之间的关系.具体研究内容如下:
在第二章中,我们研究了二部图中不含{P3,P4,P5}-因子的极值问题.汪泓教授[*** Theory 18(2)(1994)161-167]建立了给定阶数的二部图中存在{P3,P4,P5}-因子的结构性充要条件.基于该结构性质,我们给出了给定阶数的二部图包含{P3,P4,P5}-因子的边条件和谱半径条件.
在第三章中,我们研究了二部图中不含[a,b]-因子的极值问题,其中a ≤b是两个正整数.首先,我们确定了给定两个部集且不含[a,b]-因子的二部图边数的最大值,并刻画了对应的极图.在此基础上,我们确定了给定阶数且不含[a,b]-因子的二部图的最大边数,并且刻画了对应的极图.其次,我们分别确定了给定两个部集和给定阶数且不含[a,b]-因子的二部图谱半径的最大值,并且刻画了对应的极图.最后,当a=b=k时,我们还给出了最小度至少为k的平衡二部图包含k-因子的边条件和谱半径条件.
在第四章中,我们研究了二部图中不含奇(偶)[a,b]-因子的极值问题,其中a,b是有相同奇偶性的正整数且a≤b我们给出了给定阶数、最大度、最小度、边连通度的二部图中包含奇[a,b]-因子或偶[a,b]-因子的邻接谱条件,并且证明得到的界是最好可能的.
在第五章中,我们分别研究了二部图的邻接谱与结合数、韧度之间的关系.设G=(X,Y)是2n阶平衡二部图.胡智全教授、Law教授和臧文安教授[Hu,Law,*** *** Math.27(2)(2013)597-618]引入了 G 的二部结合数b'(G)的概念:如果G=Kn,n,则定义b'(G)=n,否则基于该定义,我们给出了平衡二部图的结合数至少为r的谱半径条件,其中r是正整数.Chvátal 在[Chvá*** Math.5(1973)215-228]中引入了韧度的概念:定义非完全图H的韧度为其中S为点割集且c(H-S)表示H-S的连通分支数;如果H是完全图,则定义t(/H)=∞.基于该定义,我们给出了给定阶数、最大度、最小度、边连通度的二部图的韧度为1的谱条件,并且证明得到的界是最好可能的.
在第六章中,我们总结本文的主要研究内容,并提出进一步研究的问题.