最大匹配数为q的n阶单圈图谱半径的研究

1、上海交通大学 硕士学位论文 最大匹配数为q的n阶单圈图谱半径的研究 姓名：严静 申请学位级别：硕士 专业：应用数学 指导教师： 20090101 5 最大匹配数为 q 的 n 阶单圈图谱半径的研究 最大匹配数为 q 的 n 阶单圈图谱半径的研究 摘摘 要要 谱半径是指图的邻接矩阵的特征多项式的最大特征根。研究图的谱 半径不仅有着重要的图论意义，而且在物理，化学，生物学和计算机网 络技术中有着广泛的应用。 单圈图是边数等于顶点数的简单连通图，本文主要研究最大匹配数 为q的n阶单圈图谱半径的排序问题。在 2003 年，常安,田丰 1给出了有 完美匹配的2k阶单圈图中具有最大和第二大谱半径的极图，近年来，郭 曙光 2和余爱梅，田丰3分别给出了最大匹配数为 q的n阶单圈图（简记 为( , )U n q）中具有最大和第二大谱半径的极图。 本文系统地研究了( , )U n q中谱半径的性质， 讨论了( , )U n q中的图移接 变形后的谱半径的变化规律。在此基础上给出了在( , )U n q中具有最大和 第二大谱半径的所有极图的刻画以及一个新的简单的证明；其次给出具 有第三大谱半径的所有极图的猜

2、想；特别地，刻画了( ,2)U n中具有前四 大谱半径的所有极图。 关键词：关键词：特征多项式，谱半径，单圈图，最大匹配数 6 THE STUDY OF SPECTRAL RADIUS OF UNICYCLIC GRAPHS WITH N VERTICES AND EDGE INDEPENDENCE NUMBER Q THE STUDY OF SPECTRAL RADIUS OF UNICYCLIC GRAPHS WITH N VERTICES AND EDGE INDEPENDENCE NUMBER Q Abstract The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Studying the spectral radius not only has important graph significance but also has been applied widely to fields of physics, chemistry, biology and comp

3、uter Network technology. Unicyclic graphs are connected graphs in which the number of edges equals the number of vertices. In 2003, A.Chang, F.Tian 1 gave the extremal graphs which have the largest and the second largest spectral radius among the unicyclic graphs with perfect matchings on 2k vertices. Recently, S.G.Guo 2 and A.M.Yu 3gave respectively the extremal graphs which have the largest and the second largest spectral radius among the unicyclic graphs with n vertices and edge independence

4、number q(denoted by ( , )U n q). In this paper, we investigate the properties of the spectral radius in ( , )U n q and discuss how the spectral radius of graphs changes after draft operation. Further, a new and simple proof for all extremal graphs which attains the largest (the second largest) spectral radius in ( , )U n q are presented. Moreover, we propose a conjecture on all extremal graphs with the third largest spectral radius in ( , )U n q. In particular, all extremal graphs with first fou

5、r largest spectral radius in ( ,2)U n are characterized. Key wordsKey words: characteristic polynomial, spectral radius, unicyclic graph, edge independence number 3 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名：严静 日期：2009 年 1 月 15 日 4 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全

6、部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 保密保密，在 年解密后适用本授权书。 本学位论文属于 不保密 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 严静 指导教师签名： 日期：2009 年 1 月 15 日 日期：2009 年 1 月 15 日 1 第 1 章 引言 第 1 章 引言 .1 基本概念与记号 .1 基本概念与记号 本节对论文研究涉及的基本概念及记号进行介绍。 图是图论的基本研究对象，因此我们首先给出图的一般定义和相关概念，记号。 定义 1.1 定义 1.1 称数学结构( ( ),( )GV G E G=为一个图图，其中( )V G表示G的顶点 集，( )E G表示G的边集，( )V G和( )E G之间存在着某种关系使得每条边和两个顶点 相关联， 并将这两个顶点称为这条边的端点。 我们通常用euv=来表示一条以u和v为 端点的边e。 图G中顶点集( )V G的大小称为图的阶阶，记为G；在图中与顶点u相邻的点的集 合称为u的邻域邻域，记为( )N u；与顶点u相关联的边的条数称为u的度度，记为deg( )

7、u； 度为 1 的顶点称为悬挂点悬挂点， 与该点相关联的边称为悬挂边悬挂边； 在一个顶点上连接1n条 悬挂边的n阶图称为星图星图，记为 1,1n K 或 n S 。 对于图中的某些特殊的边，我们也有确切的定义。 定义 1.2 定义 1.2 一个环环是一条边，它的两个端点是相同的；重边重边是具有同一对端点 的多重边。一个简单图简单图是不含有环和重边的图。 我们这里只研究简单图。由于图以多种形式出现，我们需要给出图的结构的有 关概念。 定义 1.3 定义 1.3 设图( ,)GV E=， 111 ( ,)GV E=，若满足 1 VV且 1 EE，则称 1 G 是 G的一个子图子图。 若 1 VV， 1 EE， 则称 1 G 是G的一个真子图真子图。 特别的， 当 1 VV=时， 称 1 G 是G的一个生成子图生成子图。 2 定义 1.4 定义 1.4 从简单图G到简单图H 的同构是一个双射 f ：( )()V GV H，使 得( )uvE G当且仅当( ) ( )()f u f vE H。如果存在从G到H 的同构，我们说“G同 构 同 构于H” ，记为GH。 我们还需要一些术语来描述图中的

8、两种路线：道路和圈以及一些相关的概念。 定义 1.5 定义 1.5 在顶边交错链 0 1 1 2kk Wv ev ee v=L中，( ) i eE G，1,2,ik=L， ( ) j vV G，0,1,2,jk=L， 且 1iii ev v =， 则称W是图G的一条道路道路， 其中允许 ij vv=， ij ee=，ij。称 0 v 是W的起点， k v 为W的终点，k为路长。各顶相异的道路称为 轨道。起点与终点重合的轨道叫做圈圈，长为k的圈称为k阶圈，记作 k C 。 对图G的任意两个顶点,u v 的距离距离是指u与v为起止点的最短路长， 记作( , )d u v ； 图的直径直径是指图的任两个顶点间的最大距离；如果图G中的每对顶点都属于某一条 道路，则称图G是连通图连通图；没有圈的连通图称为树树。本论文研究的是仅含有一个圈 的连通图，称之为单圈图单圈图，也可以定义为顶点数和边数相等的连通图。 最后我们要介绍本论文涉及到的两个很重要的概念：匹配和谱半径。 定义 1.6 定义 1.6 设M 是图( ,)GV E=的边集E 的一个子集，如果M 中任意两条边 在G中均不邻接，则称M是图G的

9、一个匹配匹配。若匹配M的某条边与顶点v相关联， 则称M饱和顶点v，并且也称顶点v是M-饱和-饱和的，否则称v是M不饱和的。如果G 的每一个顶点都是M-饱和的，则称M是G的一个完美匹配完美匹配。 定义 1.7 定义 1.7 设M是图G的一个匹配，若不存在的另外的匹配M使得 MM ，则称M 是G的最大匹配最大匹配。其中M表示匹配所包含的边数，称为匹配数匹配数。 为了更好地说明一个图，便于研究图的性质，我们常用矩阵来表示一个图。下 面我们给出简单图的三种矩阵表示。 定义 1.8 定义 1.8 设( ,)GV E=， 12 , n Vv vv=L， 12 , m Ee ee=L, 3 定义邻接矩阵邻接矩阵:( )(),1,2, ijn n A Gai jn =L，其中 1,() 0, ij ij vvE a = 否则 ； 定义关联矩阵关联矩阵:( )(),1,2, ,1,2, ijn m B Gbinjm =LL，其中 1, 0, ij ij ve b = 是 的端点 否则 ； 定义 Laplacian 矩阵Laplacian 矩阵: ( )( )( )L GD GA G=,其中 12 ( )(,) n D Gdiag d dd=L是图G的 度对角矩阵，这里 i d 是点 i v 的度。 定义 1.9 定义 1.9 设G是n阶简单图， 称邻接矩阵( )A G 的特征多项式为G的特征多 项式 特征多 项式，记为( ; )P G， ( ; )P G的特征值就称为G的特征值，因为( )A G 为实对称矩阵， 故G的特征值均为实数，可按大小顺序排列为 12 ( )( )( ) n GGG

《最大匹配数为q的n阶单圈图谱半径的研究》由会员E****分享，可在线阅读，更多相关《最大匹配数为q的n阶单圈图谱半径的研究》请在金锄头文库上搜索。