乘积图中的图因子、子式、点着色边赋权问题

来源 :南开大学 | 被引量 : 0次 | 上传用户:xuyi50488
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
自从图乘积引入到图论中,它就和图论的许多其他深刻而有趣的问题建立了联系,这个结合不仅使得图乘积成为一种对图操作的重要手段,同时在解决像Hamilton分解和Hadwiger猜想等这样著名的问题时,也激发出显著的进展,所有这些都归功于—个事实,那就是乘积图是由较小的图构造而来并且继承它们的性质.与此同时,有些由一些简单的图经过图乘积这样复杂的操作而构成的乘积图本身也成为了研究的焦点,比如,Hamming图和d-维立方体.在这个过程中,乘积图渐渐演变成解决数学中理论和应用方面问题的成熟而有效的工具.   本文将致力于在乘积图中研究一些图论中的经典问题的最新结果,其中我们研究的乘积图主要包括卡式积(口),强乘积(),字典积(o)三种.我们主要关注的是下面三个方面的问题,(1)乘积图和图因子;在这个方面,我们要分别探究乘积图的可扩性和因子临界性;(2)乘积图和子式理论;(3)乘积图中的点染色边赋权问题,本文第一章,我们简要介绍了本文将要用到的基本定义和符号.之后,我们会介绍一些相关的背景知识,包括本文主要讨论的三种乘积图,因子可扩性,因子临界性,子式和点染色边赋权等概念.在1.2节,我们简要介绍问题的相关背景还有那些曾经启发我们进行这些研究的已有的结果.   在第二章中,我们首先介绍一些匹配可扩性的结果,正是这些结果促使我们在乘积图中探究类似的问题,我们的主要工作是确定字典积图的可扩性,确切的说,两个连通图Gl和G2分别是m-可扩和n-可扩,那么它们的字典积图G20 G1是(m+1)(n+1)一可扩的,事实上,它也是2(m+1)(n+1)一因子临界的.   第三章主要包括两个问题:一个是卡式积图的因子临界性,另一个是在强乘积图中的类似问题,在强乘积中,我们试图在每种情况下证明出更好的结果.如果两个连通图G1和G2分别是m-因子临界和n-因子临界。(1)它们的卡式积G1口G2是[m+n+1]2(mn是偶数)一因子临界或者m+n+l(mn是奇数)-因子临界;以下的结果是关于强乘积图的,(2)如果m≥0,n=0,IV(G1)1≥2m+2并且IV(G2)≥4,那么GlG2是(2m+2)-因子临界的;(3)如果n=1,IvG1≥2m+3,并且m≥3或者I(G2)l≥5,那么G1G2是(2m+4-ε).因子临界,此处若m是偶数,则ε=0,否则ε=1;(4)如果m+2≤Iv(G1)≤2m+2,或n+2≤Iv(G2)l≤2n+2,那么Gl囟G2是mm因子临界;(5)如果Iv(G,)I≥2m+3并且IV(G2)l≥2n+3,那么G1G2是(mn一min因子临界.   在第四章中,我们主要考虑一些特殊的乘积图的子式问题,并且推广了早先Kotlov[31]中的结论.我们证明了对任意简单连通图G,若G是x(G)可染色的,那么GK2是图G口Qr的子式,此处Q是—个r.维立方体,且r=X(G).在本章结尾我们证明了一些强乘积图满足Hadwiger猜想.   在第五章中,我们介绍了关于乘积图与点着色边赋权问题的研究成果.点着色边赋权问题是和H-因子有着密切联系的问题,在这一章,我们主要给出了证明一些图满足点着色,6或10边赋权图的方法和充分条件.在本文的最后一节,我们要证明一些乘积图满足Karonski,Luczak和Thomason提出的1,2,3-猜想.  
其他文献
框架理论与采样定理是当前国际上研究的热点领域,框架在数学领域和工程领域都扮演着十分重要的角色.采样定理则是信号处理中常用的基本工具之一,小波框架与Gabor框架是两类十分
刻画矩阵集之间保持某些函数、子集、关系、变换等不变量的线性算子的问题被称为线性保持问题。线性保持问题是矩阵论研究领域中一个非常活跃的课题,它在微分方程,系统控制等领
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
5月14日上午,淮河防总2019年工作会议在蚌埠召开.会议深入贯彻习近平新时代中国特色社会主义思想,认真落实全国森林草原防灭火和防汛抗旱电视电话会议及全国水旱灾害防御工作
期刊
严子陵钓台这回有了碑园,历代诗人84首有关钓台的诗作被当代书家和杰出的石匠们,镌刻得如梦如画。富春江夜行到桐庐的头天晚上,就去了富春江夜游。夏季刚过,那晚凑巧是夜游的
Numerical simulation was used to estimate the temperature field within a poured concrete,mono-layer freezing-shaft lining.The affects from various factors were
本文根据RNA分子初等序列所构成的的螺旋结构的图表示的方法,在最大互不交碱基对个数的基础上,得出了一个对RNA结构的分类。我们在论文中主要研究了RNA扭结结构的渐进估计与计
作文教学是农村小学语文教学中的一个突出的难点.由于年龄小,智力发展水平较低,思维方式以形象思维为主,对抽象概括的写作,大部分学生觉得吃力.为了让每个学生学习在写作时顺