4正则无爪图的团横贯数和独立数

发布时间：2017-10-18 03:36

  本文关键词：4正则无爪图的团横贯数和独立数

  更多相关文章： 团 团横贯数 独立数 无爪图 4正则图

【摘要】：设G=(V,E)是一个简单图,C是G的一个至少有两个顶点的子图,如果C是一个极大的完全子图,则称C是图G的一个团.设D是图G的一个顶点子集,如果对于G的任意一个团C,D∩C?=?,则称D是图G的一个团横贯集.基数最小的团横贯集称为最小团横贯集,最小团横贯集的基数称为最小团横贯数,用τc(G)表示.设I是图G的一个顶点子集,如果对于任意的u,v∈I,uv/∈E,则称I是图G的一个独立集.基数最大的独立集称为最大独立集,最大独立集的基数称为独立数,用α(G)表示.顶点v∈V(G)的开邻集定义为v在G中所有邻点的集合,记为N(v).设H是一个简单图,如果图G中任意顶点的开邻集都同构于H,则称G是H邻域图.例如2K2邻域图每个顶点的开邻集导出的子图都同构于2K2.Wang等2014年已经证明了对于2连通且不含K4的4正则n阶无爪图τc(G)=?n/3?成立,并且猜想所有的不含K4的4正则n阶无爪图的团横贯数τc(G)≤(10n+3)/27.另外,Kang等2013年证明了2连通且不含K4的4正则n阶无爪图的独立数α(G)=?n/3?.进一步,他们也猜想所有的不含K4的4正则n阶无爪图的独立数α(G)≥(8n-3)/27.本文对上述Wang等和Kang等的定理分别给出了简洁的证明,并且解决了上述两个猜想.此外,我们对2K2邻域图G的团横贯数给了一个更好的上界(13n+3)/36,并对P4邻域图和C4邻域图分别给了一个刻画.
【关键词】：团 团横贯数 独立数 无爪图 4正则图
【学位授予单位】：新疆大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要2-3
• Abstract3-5
• 第一章 引言5-9
• 1.1 基本概念5-6
• 1.2 问题综述6-9
• 第二章 4正则无爪图上的团横贯数和独立数9-14
• 2.1 预备知识9
• 2.2 4正则无爪图上的团横贯数9-13
• 2.3 4正则无爪图上的独立数13-14
• 第三章 领域图的简单刻画14-17
• 参考文献17-20
• 硕士期间发表论文清单20-21
• 致谢21-22

【共引文献】

中国期刊全文数据库 前10条

1 杨大庆;线图的r-覆盖[J];福州大学学报(自然科学版);2005年02期

2 ;The Existence of Even Regular Factors of Regular Graphs on the Number of Cut Edges[J];Acta Mathematica Sinica(English Series);2010年12期

3 Ding Guo WANG;Er Fang SHAN;Zuo Song LIANG;;On the Clique-Transversal Number in(Claw,K_4 )-Free 4-Regular Graphs[J];Acta Mathematica Sinica(English Series);2014年03期

4 Hong Liang LU;Wei WANG;Yuqing LIN;;On Edge Connectivity and Parity Factor[J];Acta Mathematica Sinica;2015年05期

5 ;Minimal regular 2-graphs and applications[J];Science in China(Series A:Mathematics);2006年02期

6 范红兵;刘桂真;刘季平;;极小正则2-图及其应用[J];中国科学(A辑:数学);2005年11期

7 杜彩凤;;立方图中的路因子和圈因子[J];科学技术与工程;2010年27期

8 南小康;;3-正则图的1-因子与割边数[J];兰州大学学报(自然科学版);2008年S1期

9 马京成;马登举;朱s，

本文编号：1052725