ABSTRACT

A chord is an edge between two vertices of a cycle that is not an edge on the cycle. If a cycle has at least one chord, then the cycle is called a chorded cycle. The minimum degree condition is given for a bipartite graph to contain vertex-disjoint chorded cycles containing specified vertices.

Keywords:Vertex-Disjoint Chorded Cycles, Bipartite Graphs, Minimum Degree

二部图中过特定点的点不交弦圈

蔺逍遥，高云澍

宁夏大学数学统计学院，宁夏 银川

收稿日期：2018年4月11日；录用日期：2018年4月21日；发布日期：2018年4月28日

摘 要

弦是指连接圈上的两个点构成的一条边，使得这条边不属于圈上。如果一个圈至少有一条弦，那么我们称这个圈为弦圈。本文给出了二部图中过含特定点集点不交弦圈的最小度条件。

关键词 :点不交弦圈，二部图，最小度

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文只考虑有限的简单无向图。设G表示图，且令, , ,和分别是图G的点集，边集，最小度，点u的度数和与u相邻的点的集合。完全图是指图中的任意两点之间都有边。若图G是非完全图，定义

若图G是完全图，则令。长为l的圈叫做l-圈。文中未给出的定义和术语参考文献 [1] 。

关于图中过所有顶点的圈(哈密尔顿圈)的研究最早始于Dirac [2] ，他给出了著名的Dirac型条件：

定理1.1： [2] 设G是一个阶数的图且，则G包含哈密尔顿圈。

1963年，Moon和Moser [3] 给出了二部图中存在哈密尔顿圈的Dirac型条件：

定理1.2： [3] 设是一个二部图，且。如果，则G包含哈密尔顿圈。

图G是泛圈的当且仅当图G包含任意长度的圈。文献 [4] 和 [5] 给出了二部图是泛圈的相关结果。

定理1.3： [4] [5] 设是一个二部图，且。若G包含哈密尔顿圈使得，则图G是泛圈的；如果G包含哈密尔顿圈且G边数

多于，则图G是泛圈的。

关于图的哈密尔顿性质的其他结果，我们推荐读者参阅李皓的综述文章 [6] 。给定圈C，称中的边为弦。若圈C包含弦，则称圈C为弦圈。显然，若图G中存在弦圈C，则其一定包含偶长圈。Cream和Gould等人 [7] 证明了图G的Dirac型条件亦可以保证G中存在过特定点的限定长度的点不交弦圈。

定理1.4： [7] 设G是一个阶数的图，对任意的整数k，。如果，那么对G

的任意k个不同的点，存在k个点不交的弦圈使得，并且对所有的，有。

本文的主要目的是证明二部图图G的Dirac型条件亦可以保证图G中存在过指定点的限定长度的点不交弦圈。我们得到了如下的结果：

定理1.5：设是一个二部图，且，其中k为任意的正整数。如果，则对G的k个不同的点，G中存在k个点不交的弦圈，使得任意的，

且。

2. 定理1.5的证明

证明：首先证明时定理成立，此时。首先证明G是泛圈的。由定理1.2知，图G包含哈密尔顿圈。由定理1.3和最小度条件知，图G中任意一对邻接点的度和为。因此，结合握手定理，易得

,

由上式得到，于是，由定理1.3，图G是泛圈的。我们考虑图G中的6-圈。不失一般性，不妨设。如果C是弦圈，那么定理对成立。假设C不是弦圈，则。

断言2.1：。

证明：反证法。假设。由于，则

,

由上式，，于是我们可以把剖分成两部分，不妨记为A和B，使得且。假设和在中有公共的邻点，

不妨设为u，注意到，不失一般性，不妨设存在使得。此时，

为通过的8-圈，其中为弦，定理证毕。因此，和在中没有公共的邻点。于是，仿照上面的部分，把剖分成两部分，不妨记为D和F，使得且。不失一般性，不妨设且，显然，y在中有邻点，不妨设存在使得，则为通过的8-圈，其中为弦，定理证毕。故断言2.1成立。

根据对称性和断言2.1，易得如下的结论。

断言2.2：且。

不妨令分别表示中点和的公共邻点。如果，则是包含的6-圈，其中为弦。如果，令z表示中的公共邻点，则是包含的8-圈，其中为弦。故时定理成立。因此，。我们使用反证法证明。

假设时定理不成立。令G是一个边极大的反例，为G中任意的k个不同点。因为阶数至少为6k的完全二部图包含k个点不交的满足定理条件的弦圈，故假设G不是完全图。令是G中两个不相邻的点且。令。则由G的边极大性，不是反例，故包含k个点不交的满足定理条件的弦圈，记为。不失一般性，不妨设G包含个不交的弦圈，使得对，，，并且。

我们选择使得是最小的。 (1)

令，，则由和，可得

,

断言2.3：对任意的及，有。

证明：假设存在及某个，使得。我们只需考虑的情况。在这种情况下，我们找到一个包含特定点或的弦圈使得，用代替，则与(1)的选取矛盾。

令且。不失一般性，不妨设。令。首先考虑的情形。如果，那么且是弦。如果，那么且是弦。

因此，显然。如果，那么是包含但不含的6-圈且是弦。如果，那么是包含但不含的6-圈且是弦。如果，那么是包含但不含的6-圈且是弦。如果，那么是包含但不含的6-圈，使得是弦。断言2.3证毕。

因为，由断言2.3，对于任意的，，于是

,

不失一般性，不妨设且令。令分别是的邻点，且。

情况1：存在两个不同的点，使得。

不失一般性，不妨设且。于是有

于是，

从而，与矛盾。

情况2：对不同的点，至少存在两对点和，使得，且。

不失一般性，令，也就是，且。则是包含的6-圈且是弦。

情况3：在中，点只有一个公共邻点。

此时，由于

则

从而，与矛盾。至此，定理1.5证毕。

基金项目

国家自然科学基金(11561054)。

文章引用

蔺逍遥,高云澍 . 二部图中过特定点的点不交弦圈
Vertex-Disjoint Chorded Cycles through Specified Vertices in Bipartite Graphs[J]. 应用数学进展, 2018, 07(04): 413-417. https://doi.org/10.12677/AAM.2018.74051

参考文献