Advances in Applied Mathematics
Vol.07 No.04(2018), Article ID:24677,5
pages
10.12677/AAM.2018.74051
Vertex-Disjoint Chorded Cycles through Specified Vertices in Bipartite Graphs
Xiaoyao Lin, Yunshu Gao
School of Mathematics and Statistics, Ningxia University, Yinchuan Ningxia
Received: Apr. 11th, 2018; accepted: Apr. 21st, 2018; published: Apr. 28th, 2018
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
参考文献
- 1. Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Elsevier, New York. https://doi.org/10.1007/978-1-349-03521-2
- 2. Dirac, G.A. (1952) Some Theorems on Abstract Graphs. Proceedings of the London Mathematical Society, 2, 69-81. https://doi.org/10.1112/plms/s3-2.1.69
- 3. Moon, J.W. and Moser, L. (1963) On Hamiltonian Bipartite Graphs. Israel Journal of Mathematics, 1, 163-165. https://doi.org/10.1007/BF02759704
- 4. Entringer, R.C. and Schmeichel, E.F. (1988) Edge Conditions and Cycle Structure in Bipancyclic Graphs. Ars Combinatoria, 26, 229-232.
- 5. Schmeichel, E.F. and Mitchem, J. (1982) Bipartite Graphs with Cycles of All Even Lengths. Journal of Graph Theory, 6, 429-439. https://doi.org/10.1002/jgt.3190060407
- 6. Li, H. (2013) Generalizations of Dirac’s Theorem in Hamiltonian Graph Theory—A Survey. Discrete Mathematics, 313, 2034-2053. https://doi.org/10.1016/j.disc.2012.11.025
- 7. Cream, M., Faudree, R., Gould, R. and Hirohata, K. (2016) Chorded Cycles. Graphs and Combinatorics, 32, 2296-2313. https://doi.org/10.1007/s00373-016-1729-4