资源描述：
《拟树图与拟单圈图的排序及优超定理.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、分类号密级公开UDC学号20150713002青海师范大学硕士学位论文拟树图与拟单圈图的排序及优超定理研究生姓名罗可导师姓名(职称)郭曙光，教授申请学位类别理学硕士学科专业名称基础数学研究方向名称代数图论论文提交日期2018年3月论文答辩日期2018年月学位授予单位青海师范大学学位授予日期答辩委员会主席评阅人，青青青海海海师师师范范范大大大学学学学学学位位位论论论文文文独独独创创创性性性声声声明明明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果.尽我所知,除了文中特别加以标注和致谢的地方外,论
2、文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得青海师范大学或其它教育机构的学位或证书而使用过的材料.与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意.研究生签名：日期：青青青海海海师师师范范范大大大学学学学学学位位位论论论文文文使使使用用用授授授权权权声声声明明明青海师范大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档,可以采用影印、缩印或其他复制手段保存论文.本人电子文档的内容和纸质论文的内容相一致.除在保密期内的保密论文外,允许论文被查阅和
3、借阅,可以公布（包括刊登）论文的全部或部分内容.论文的公布（包括刊登）授权由青海师范大学研究生部办理.研究生签名：导师签名：日期：拟树图与拟单圈图的排序及优超定理中文摘要对于一个非增的非负整数序列=(d1;d2;:::;dn),若存在一个图G以为度序列,则称是可图的.C={G:G表示以为度序列的n阶简单连通图}.若一个连通图G中存在一个点v∈V(G),使得G−v是一棵树,则称G为拟树图.若一个连通图G中存在一个点v∈V(G),使得G−v是一个单圈图,则称G为拟单圈图.单锥图是完全图K1和连通图G的联图.单锥树是
4、完全图K1与树Tn−1的联图.单锥单圈图是完全图K1与单圈图Un−1的联图.1981年,国际著名图谱专家Cvetkovic´提出了图谱理论中进一步研究的十二个方向,其中之一就是“依图的谱对图进行分类和排序”.此后这一问题,特别是图依谱半径的排序问题被广泛研究,至今仍为图谱研究的热点.2006年,Bıyıkoglu˘和Leydold猜想:“设和′是两个不同的非增可图度序列,▹′,G′′和G分别为C和C′中谱半径最大的图,则(G)<(G).”几乎同时,他们证明了这一猜想对树成立.此后,刘木伙等人证明了这一猜想
5、对单圈图和双圈图成立，并举例说明这个猜想并非对所有的图都成立.本文进一步研究图依谱半径排序和Bıyıkoglu˘和Leydold猜想,主要内容如下:第一章主要介绍图依谱半径排序和Bıyıkoglu˘和Leydold猜想研究的背景和主要进展,概述本文得到的主要结果.第二章介绍结果证明过程中用到的一些概念、记号和引理.第三章研究拟树图和拟单圈图按其谱半径排序.确定了谱半径排在前五位的拟树图和谱半径排在前七位的拟单圈图.第四章研究单锥图的谱半径的优超定理.首先,研究了给定度序列的单锥图中谱半径最大的图具有的性质.其次,证明Bı
6、yıkoglu˘和Leydold的猜想对单锥树和单锥单圈图成立.关关关键键键词词词:拟树图,拟单圈图,度序列,优超IOrderingandmajorizationtheoremsofquasi-treeGraphsandquasi-unicyclicGraphsAbstractAnon-increasingsequence=(d1;d2;:::;dn)iscalledgraphicifthereexistsagraphGhavingasitsdegreesequence.WeuseCtodenotetheclass
7、ofconnectedgraphswithdegreesequence.AconnectedgraphGiscalledaquasi-treegraph,ifthereexistsavertexv∈V(G)suchthatG−visatree.AconnectedgraphGiscalledaquasi-unicyclicgraph,ifthereexistsavertexv∈V(G)suchthatG−visaquasi-unicyclicgraph.Asingle-conegraphisthegraphobtain
8、edbyjoiningeachvertexinacompletegraphK1toeachvertexinaconnectedgraphGofordern−1.Asingle-conetreeisthegraphobtainedbyjoiningthevertexinacompletegraphK1toeachver
