图的可迹性与泛圈性的谱充分条件

论文摘要

判断一个图是否是哈密尔顿图是一个NP-完全问题,已经受到图论工作者的广泛关注.由于图的谱能够很好地反映图的结构性质且便于计算,所以利用谱图理论来研究图的结构性质逐渐成为近些年的一个研究热点.图的邻接（无符号拉普拉斯）谱半径定义为该图对应的邻接（无符号拉普拉斯）矩阵的最大特征值.图的能量定义为该图对应的邻接矩阵所有特征值的绝对值之和,可以被视为是一个基于图谱的不变量.如果一个图含有一条过所有顶点的路,则称这个图是可迹图.如果一个图含有所有可能长度的圈,则称这个图是泛圈图.本文主要研究图的可迹性与泛圈性这两个问题,具体内容安排如下:第一章,首先介绍本文的研究背景与意义,然后介绍本文所涉及的概念、定义和术语,最后介绍本文研究问题的进展以及主要结论.第二章,首先利用拟补图的能量刻画了拟平衡二部图的可迹性.随后引入图的最小度条件,利用带有最小度的能量刻画了拟平衡二部图的可迹性.第三章,首先通过优化图的泛圈性的边数条件,考虑边数与极端谱之间的联系,分别利用图的谱半径和无符号拉普拉斯谱半径刻画了图的泛圈性和平衡二部图的偶泛圈性.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   §1.1 研究背景与意义
•   §1.2 概念与记号
•   §1.3 研究问题的进展及本文主要结论
• 第二章 可迹图的谱充分条件
•   §2.1 基本引理
•   §2.2 拟平衡二部图可迹的能量条件
•   §2.3 具有最小度的拟平衡二部图可迹的能量条件
• 第三章 泛圈图的谱充分条件
•   §3.1 基本引理
•   §3.2 图的泛圈性的谱充分条件
•   §3.3 平衡二部图的偶泛圈性的谱充分条件
• 符号说明
• 参考文献
• 攻读硕士学位期间发表文章情况
• 致谢

文章来源

类型: 硕士论文

作者: 徐弈

导师: 余桂东

关键词: 二部图,谱半径,无符号拉普拉斯谱半径,可迹性,泛圈性

来源: 安庆师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 安庆师范大学

分类号: O157.5

总页数: 68

文件大小: 2339K

下载量: 9