星集理论与图重建问题的研究

论文摘要

图谱理论是图论的一个重要的研究方向,它在量子化学、计算机科学、通讯网络等方面有广泛的应用.星补理论是图谱理论中一个重要的研究课题,它在图的同构和强正则图的存在性等问题中有很好的应用.当给定特征值和星补时,利用星补技术构建极大图的研究一直是星补理论的研究热点.本文研究了星图和完全二部图作为星补时的极大图构造问题.具体考虑了特征值为-2,星图作为星补时的极大图构造问题,以及对于所有的特征值,完全二部图作为星补时的极大正则图构造问题.本文主要内容如下:·第一章介绍了本课题的研究背景和相关概念以及一些基本理论.·第二章综述了近几年来星补理论的一些研究进展.主要关于以下三个方面:特征值重数,即星集中顶点个数的上界问题;给定星补时的极大正则图的构造问题;当次大特征值为1,连通图作为星补时的极大图构造问题.·第三章研究了特征值为-2,星图Sm作为星补时的极大图的构造问题.首先,利用重建定理证明了特征值为-2,星图Sm中只有S3,S4,S13,S14,S21,S23,S30可以作为星补.然后,当星补H是S3,S4,S13,S14,S21,S23,S30中任意一个时,确定了所有的良好集U（?）V（H）.最后,当特征值为-2,分别刻画了以S3,S4,S13,S21为星补时的极大图,并证明了-2是以S13,S14,S21,S23,S30为星补时所得到的极大图的次小特征值.·第四章研究了以完全二部图K2,s（s≥2）为星补时的极大正则图的构造问题.首先,证明了特征值为-2时,完全二部图K2,s（s≥2）不能作为星补.然后,考虑特征值μ≠1和-2时,确定了星集中可添加的顶点类型,进一步地刻画了以K2,s（s≥2且≠5）为星补时的最大正则图.最后,当特征值为-1,以完全二部图K2,s（s≥2）为星补时的极大正则图也得到了完全刻画.

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景
•   1.2 基本概念
•     1.2.1 星集和星补的定义
•     1.2.2 星集和星补的基本性质
• 第二章 研究现状及本文主要结论
•   2.1 特征值重数的上界问题
•   2.2 给定星补时的极大正则图的构造问题
•   2.3 给定次大特征值1,以连通图为星补时的极大图的构造问题
•   2.4 本文主要结论
• m为星补时的极大图的构造问题'>第三章 以S_m为星补时的极大图的构造问题
•   3.1 准备工作
•   3.2 主要结论
• 2.s（s≥2）为星补时的极大正则图的构造问题'>第四章 以完全二部图K_2.s（s≥2）为星补时的极大正则图的构造问题
•   4.1 准备工作
•   4.2 主要结论
• 第五章 总结及展望
• 参考文献
• 作者攻读硕士学位期间完成的论文
• 致谢

文章来源

类型: 硕士论文

作者: 赵清清

导师: 袁西英

关键词: 星集,星补,特征值,极大图

来源: 上海大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 上海大学

分类号: O157.5

DOI: 10.27300/d.cnki.gshau.2019.000308

总页数: 42

文件大小: 1546K

下载量: 9