英语原文共 32 页，剩余内容已隐藏，支付完成后下载完整资料

---

环和路径上Erdouml;s-Gallai定理体现的稳定性

摘要

Erdouml;s-Gallai定理指出当时，如果一个图的每一个节点的度至少是，那么它一定含有个节点的路径。这个结论可以通过Kopylov的加强结果得到：如果是奇数，，并且是一个个节点、（去掉至少2个顶点后原图才不连通）、 条边的图，除非，否则一定含有长度至少为的环。

在这篇文章我们证明了带稳定性的Erdouml;s-Gallai定理：对任意的并且每一个节点、（去掉至少2个顶点后原图才不连通）当边满足的图要么含有一个长度至少为的环，要么含有个节点的集合，且原图去掉集合中点后构成一个星图森林。尤其当时，我们证明，其下界满足。

关键字：Turaacute;n 问题；路径；环

内容简介

图论中Turaacute;n型问题的研究奠定了超组合学的基石。在超图论理论中的一个极其重要的问题就是探讨一个不含个节点的环的阶图边的数量的最大值。该问题被Turaacute;n提出[10]，最终被Erdouml;s和Gallai解决[7] 。

定理1.1（Erdouml;s和Gallai [7]）设图阶图满足，则一定含一个节点的路径。

如果可以被整除，那么个节点的图可以分成若干的的完全图，此时边等于，故上述完全图之间中一定边，有那么该定理最有可能成立。为了以上结果，Erdouml;s和Gallai观察到：如果阶图不含阶路径，那么我们新增加一个节点并且与其他节点连接，这样我们就得到图阶图并且，它并不包含长度大于或等于的环。这样定理1.1 就是下述定理的结果；

定理1.2（Erdouml;s和Gallai [7]）设图阶图满足，则一定含长度至少为的环。

如果可以被整除，那么阶图中这个节点可以分成若干个阶的环，当当剩下的第个节点与上面的每一个节点都相连此时，边数为，此时最有可能含长度至少为的环。令表示没有长路路径的阶图边的最大数量；定理1.1表明取等当且仅当可以被整除。Erdouml;s-Gallai定理的几个证明和完善分别由Woodall [16]、Lewin [12]、Faudree 和Schelp [8,9]和Kopylov [11]得到，文献 [10]提供了更好的细节。最强的版本被Kopylov得到[11]。为了描述他的结果，我们要构造下面的图；假设，定义阶图：的节点集分成集合，它的边集由集合之间所有的边以及中所有的边组成；

定理1.3 （Kopylov [11]）令 ，如果阶、所有节点度不为0的图不含长度大于等于的环，则有

取等当且仅当或。

本文中我们要证明的是带稳定性版本的定理1.1和定理1.3。这里所说的星林（star forest）是指星图之间不相连的图集。

定理 1.4 令，并且阶、所有节点度不为0图是一个不包含长度大于等于的环。则当且仅当满足下面两条件任意一个

（a）并且；

（b）并且存在时，构成一个星图林。

上面的结论在以下情况最有可能成立：注意到不含长度大于等于的环并且它不是的子图；对任意，一定含一个环。因此定理1.4的陈述当并不成立。因此满足上述定理最有可能。因为

定理1.3中Kopylov的边界与定理1.4的不同即：

有意思的是固定时上面的差值除以当时并不趋于0。

我们将需要证明一个更详细版本的定理1.4，此版本将满足下面针对图（去掉至少3个顶点后原图才不连通）的推论。

推论1.5令 ，如果阶（去掉至少3个顶点后原图才不连通）的图不含长度大于等于的环，则有时当且仅当。

类似定理1.2可以导出定理1.1，定理1.4可以给出一个关于路径的稳定性定理：

定理1.6令，如果阶联通图不包含阶路径，则当且仅当满足下面任一条件；

（a）

（b）并且存在时，构成一个星图林。

实际上，记图为一个阶、连通的、边数超过的图通过增加一个与所有节点都相连的节点构成图。则是（任意2阶子图连通）、边数大于的图。如果不含阶路径，则不含长度大于等于的环。在定理1.4中，满足条件（a）或条件（b），等同于定理1.6中满足条件（a）或条件（b），则推论1.5可以导出

推论1.7 令 ，如果图是阶、（去掉至少2个顶点后原图才不连通）并且不包含阶路径，则当且仅当。

本文组织：关于定理1.4的证明将利用第2节中列举的许多结果和第3节中关于边收敛的引理。然后在第4节中我们描述几个特殊的图系、陈述并注明一个更完备的定理4.1，也就是时。最后在第5节中我们会证明当时定理4.1的类似情况。我们所说的（去掉至少2个顶点后原图才不连通）不含长度大于等于6的环。

符号说明：本文中所有的符号都是图论中的标准符号：给定一个图，表示节点的领域，也就是与连接的节点集，简记为，节点的闭领域记为，节点的度记为。给定，我们定，， ；对于，表示包含边的三角形数量，并且。图中节点度的最小值记为。对于边，表示合并边为一个节点后的图，并用表示新的节点。图中最大换的长度记为，。表示阶完全图，表示由节点子集为节点组成的完全图。给定相互没有连接的图，表示节点集为边集为的图。已知表示一个图，表示图的补。对于一个正整数，表示个子图组成的图，每一个子图都与同构。对于交集为空的，表示由节点子集为节点、图中节点子集之间的边为边的图，另外表示由节点集在中的子图。

经典的定理

我们需要大量稠密图中关于长路径和环的定理结论。下述内容是对（去掉至少2个顶点后原图才不连通）图的一个著名结论“阶非哈密顿图（哈密顿图存在哈密顿回路：存在通过的每个节点一次且仅一次的回路）有至多 条边”的一个扩充。

定理2.1（Erdouml;s [6]）令为整数，且

则对于每一个阶图满足一定为哈密顿图。

根据图和图 ，的边界很明确。对每一个（去掉至少2个顶点后原图才不连通）图，由于，我们有下面的推论：

定理2.2（Erdouml;s [6]）如果且图是一个阶、（去掉至少2个顶点后原图才不连通）的非哈密顿图（哈密顿图指存在哈密顿回路：存在通过的每个节点一次且仅一次的回路），则 ，取等号当且仅当。

显然对于图，如果则包含长度至少为的环。对此Dirac证明了关于（去掉至少2个顶点后原图才不连通）图的一个更强的结论：

定理2.3（Dirac [4]）如果图是（去掉至少2个顶点后原图才不连通）的，则。

Kopylov [11]根据Poacute;sa的观点对上面的结果做了如下的加强：

定理2.4（Kopylov [11]）如果是（去掉至少2个顶点后原图才不连通）的，是到路径的长度的节点集，则。

定理2.5（Chaacute;vtal [3]）令阶图节点度满足：。如果图不是哈密顿图，则存在某个使得。

图的阶闭包指的是节点数为唯一的最小的图满足：；简记为，对于原图可以通过递归算法得到：将不相邻的节点（度总和至少为）连接起来。

定理2.6（Bondy和Chaacute;vtal [1]）如果是哈密顿图，那么也是哈密顿图。因此，如果，那么也是哈密顿图。

考虑一个图给定的节点之间的长路径，Lovaacute;sz [13]指出：（去掉至少2个顶点后原图才不连通）图除了节点外其他节点度至少为，那么一定存在长度至少为的到的路径。该结果被Enomoto加强。下面的定理来自文献[5]中的推论1：

定理2.7（Enomoto [5]）令，假设阶图为3-connected（去掉至少3个顶点后原图才不连通）的，对于所有不相邻的不同节点满足，则对于图所有的不同节点，一定存在长度至少为从到的路径。并且如果存在不同节点，使得不存在长度至少为从到的路径，则要么

或者（为一个整数）

关于上面结果更深层次的加强由Bondy和Jackson [2]给出。最后，我们需要关于包含给定边集的环的一些结论。下面的结果由Poacute;sa [15]得到：

定理2.8（Poacute;sa [15]）令，阶图满足

则对于每一个包含中条边的线性森林，图有一个包含所有边的哈密顿环。

下述是关于由两部分子图组成的图的类似于Poacute;sa的结果的结论，是文献[17]定理7.3的一个简单推论。

定理2.9（Zamani和West [17]）令，是由节点子集为节点组成的完全图的子图满足。则对于每一个线性森林包含至多条边，中一定存在一个哈密顿环包含中的所有边。

我们将仅仅使用定理2.9的部分结果：

推论2.10令，是的子图，包含至少条边。是包含至多条边和至多两个部分的线性森林，则有一个哈密顿环包含中的所有边。

关于边收缩的引理

证明定理4.1的一个最重要的部分就是要分析图中边的收缩。也就是说，我们要根据一些基本原则来收缩边集。我们用收缩的拓展理论来证明Erouml;ds-Gallai定理的想法启发于Lewin [12]。本节中，我们列举一些关于收缩的基本的构造性引理。

引理3.1令，图是阶（去掉至少2个顶点后原图才不连通）的。，如果，一定存在使得是（任意2阶子图连通）的。

证明：令，已知节点是图收缩节点得到的。由于是2-connected（去掉至少2个顶点后原图才不连通）的，是连通的。如果是中的一个割点（去掉该顶点和与之相关联的边后原图连通分支增加），则在中也是一个割点，矛盾，故中唯一的割点为。因此如果引理不成立，则是中唯一的割点，这意味着都是图中割点集合。

选择便于缩小中最小的连通分支节点数。令为中这样的一个连通分支的节点集，并且。因为是（去掉至少2个顶点后原图才不连通）的，节点有一个邻接点和。因为。但是中每一个不包含连通分支的节点集包含在中，这与的定义矛盾。

该引理可推导于下述引理：

引理3.2令，图是阶（去掉至少2个顶点后原图才不连通）的，如果，则一定存在是2-connected的。

证明：如果，等同于引理3.1。假如，意味着是完全图，那么收缩任何与相连的边等同于等同于去掉。令，因为并且是完全图，中任何任何割点（去掉该顶点和与之相关联的边后原图连通分支增加）也是中的割点。

图中对于，表示包含边的三角形数量，并且。当我们收缩图中的一条边，每一个节点的度要么不改变要么减1，另外中的度至少是，故而

类似

假如我们一次一步的收缩2-connected图的边，总是选择一条边使得

（a）新图是2-connected（去掉至少2个顶点后原图才不连通）的，

（b）含边的三角形数量最少，

（c）边的收缩到尽可能度小的节点

引理3.3是一个正整数，假设2-connected（去掉至少2个顶点后原图才不连通）的图是2-connected图按照上面的规则（a）-（b）通过收缩边为节点得到的。如果至少有个节点度至多为，则要么要么也有一个节点度至多为。

证明：因为是2-connected的，。如果有一个节点度小于，根据式(3.1)定理成立。令表示中度恰好为的节点集合，并假定，令，假定引力不成立，则

aq

情况1：；根据式(3.3)，边属于至少个三角形并且第三个顶点在。根据规则（c）和之间的对称性，我们假定，由于是2-connected（去掉至少2个顶点后原图才不连通）的，任何不是割点，甚至边不是割边。实际上，是的所有邻接点的邻接点，因此的所有邻接点在同一个连通分支中，同理在中也一样，并且lt;

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[137738]，资料为PDF文档或Word文档，PDF文档可免费转换为Word