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