论文部分内容阅读
自从图乘积引入到图论中,它就和图论的许多其他深刻而有趣的问题建立了联系,这个结合不仅使得图乘积成为一种对图操作的重要手段,同时在解决像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-猜想.