论文部分内容阅读
谱图理论是代数图论与组合矩阵论中的一个重要研究领域,其核心是通过图的相关矩阵所描述的谱参数来刻画图自身的结构性质,并研究图的谱参数与其结构之间的内在联系.本论文主要借助于图变换、函数构造与求导法、数学归纳法等方法和技巧,研究图的谱参数(包括邻接谱、距离谱、正规化拉普拉斯谱)、结构参数及相关问题.具体内容包括:·在第二章中,给定任意一个简单的连通图G,我们分别确定Tk(G)和Qk(G)的正规化拉普拉斯谱与G的正规化拉普拉斯谱之间的关系,其中k≥2.在此基础之上,第r次迭代的k-三角形图TTk(G)和第r次迭代的k-四边形图QTk(G)的正规化拉普拉斯谱、度积基尔霍夫指数、Kemeny常数以及支撑树的数目的表达式也被分别给出.我们的结果拓展了[Xie et al.,Appl.Math.Comput.273(2016)1123-1129]和[Li et al.,Appl.Math.Comput.297(2017)180-188]中的结果.·在第三章中,我们首先给出广义二面体群上Cayley图是整谱图的充分必要条件,该结果很自然地推广了[J.Algebraic Combin.47(2018)585-601]中的主要结论.其次给出任意有限群上Cayley图的距离矩阵的分解公式,利用该分解公式得出广义二面体群上Cayley图是距离整谱图的充分必要条件.同时,得出一些特殊条件下的广义二面体群上Cayley图的整性和距离整性的一些简单的充分必要条件,根据它们可以构造无穷多类整的和距离整的Cayley图.最后又给出广义二面体群上Cayley图的整性和距离整性等价的几个充要条件.·在第四章中,我们考虑定向图的斜秩与其底图的独立数和圈空间维数之间的关系.给定任意一个简单的连通图G,确定sr(Gσ)+2α(G)的下确界并刻画达到下界的极图.在该结果的基础上,得出sr(Gσ)+α(G),sr(Gσ)-α(G)以及sr(Gσ)/α(G)的下确界并且分别刻画达到下确界的极图.·在第五章中,我们首先完整给出Q(G)上随机游走的概率转移矩阵的特征值.其次,确定Q(G)和G中任意两点撞击时间的期望值之间的关系,并利用该结果推导出Q(G)和G中任意两点电阻距离之间的关系,其中G为任意的简单连通图.最后,作为应用,Q(G)与G的度积基尔霍夫指数、Kemeny常数以及支撑树数目之间关系也将被分别给出.·在第六章中,我们探讨单圈图上随机游走的撞击时间,基尔霍夫指数,及其与其他的不变量之间的密切联系.同时分别刻画n阶单圈图中任一顶点的覆盖成本和反覆盖成本的上、下确界及其相应的极图.·在第七章中,我们总结本文的主要内容,并提出一些进一步研究的问题。