步长为1和4的循环图的k-偶匹配可扩性∗

惠志昊

（平顶山学院数学与信息科学学院 平顶山 467000）

步长为1和4的循环图的k-偶匹配可扩性∗

惠志昊

（平顶山学院数学与信息科学学院 平顶山 467000）

称图G是偶匹配可扩的，是指G的每一个偶匹配M都可以扩充为G的一个完美匹配。判定图是否含有基数为k的偶匹配是NP-困难问题，该文主要刻画了循环图C2n(1，4)的k-偶匹配可扩性。

完美匹配；偶匹配可扩；k-偶匹配可扩；循环图

1 引言

设图G是一简单的且有完美匹配的连通图。称图G是k-偶匹配可扩的，是指G的每一个基数不大于k(1≤k≤(|V(G)|-2)2)的偶匹配M 都可以扩充为G的一个完美匹配。本文中没有加以说明的概念和术语可参考［1］，关于图的匹配可扩性和k-偶匹配可扩性已经有很多结论［3～11］。在文献［7］中证明了判定图G是否含有基数是k的偶匹配是NP-困难问题；判定图G是否是偶匹配可扩的是co-NP-困难问题。本文主要根据图的k-偶匹配可扩性完全刻画了循环图C2n(1，4)的偶匹配可扩性。这对我们进一步判定偶匹配可扩图有很重要的意义。

定义1 对一个有 2n 个顶点 x0，x1，x2，…， x2n-1的图G，如果 xixj是图G的边，当且仅当i-j≡±1(mod2n)，或者 i-j≡±k(mod2n)，则称图 G为步长为1和 k 的循环图，记为 C2n(1，k)［2］。

令 Zn为模 n的剩余类加群，即Zn={0，1，2，…，n-1}运算取模 n的加所构成的群。若S⊆Zn-{0}，且S=-S，则称S为Zn的特征集。若 S 为 Zn的特征集，则有 j1，j2，j3，…，jr⊆{1，2，…，[n 2]} ，S={j1，j2，j3，…，jr，n-j1，n-j2，n-j3，…，n-jr}，其中[n 2]表示不超过n 2的最大整数。

定义 2［2］对上述 Zn，S ，若图 G=(V，E)满足点集V(G)=Zn，边集 E(G)={(i，j)|j-i∈S}，则称 G为Zn上关于特征集S的循环图，记为Cn(j1，j2，j3，…，jr) ，其 中 j1＜j2＜j3＜…＜jr，并 称j1，j2，j3，…，jr为生成元。

引理1［1］（Tutte定理） 图G中存在完美匹配，当且仅当对于任意的S⊆V(G)，ο(G-S)≤ ||S，其中ο(G)表示G的奇分支数。

引理2［3］图G是偶匹配可扩的，当且仅当对于 G的任意偶匹配 M 的 S⊆V(G)V(M)，有ο(G-V(M)-S)≤ ||S 。

引理3［3］图G是偶匹配可扩的，当且仅当对任意的 S⊆V(G)，ο(G-S)≤ ||S-2mb(S)。其中mb(S)表示G[S]中最大偶匹配的基数。

2 循环图C2n(1，4)的k-偶匹配可扩性

定理1 循环图Cn(1，n 2)可分解为一个1-因子和2-因子的边不重的并。

定理2 循环图C8(1，4)仅是1-偶匹配可扩图。

证明：设循环图 C8(1，4)的顶点为 x0，x1，x2，…，x7按逆时针顺序循环排列，且顶点下标按模8加运算。

如果取图C8(1，4)的一基数为 3偶匹配M={x0x1，x3，x4，x5，x6} ，则 C8(1，4)-V(M)有两个孤立点x2和x7。因此，C8(1，4)不是偶匹配可扩图。

任取循环图C8(1，4)的一偶匹配M ，我们根据它的基数判定该图的k-偶匹配可扩性：

设M 是循环图C8(1，4)的一基数为1的偶匹配，记为M={xixj}。由定理1知循环图C8(1，4)可分解为一个1-因子和2-因子的边不重的并，记N={x0x4，x1x5，x2x6，x3x7} ，C8=x0x1x2…x7x0。 易知，M⊂N或者M⊂E(C8)。从而，知图C8(1，4)的偶匹配M可以扩充为它的一个完美匹配。因此，循环图C8(1，4)是1-偶匹配可扩的。

设M 是循环图C8(1，4)的一基数为2的偶匹配，记为M={xixj，xsxt}。若M 中的元素仅是步长为1的边，令M={ }xixi+1，xjxj+1。当 j=i+3时，则C8(1，4)-V(M)同构于 K1，3，故图 C8(1，4)-V(M)不存在完美匹配。因此，C8(1，4)必不是2-偶匹配可扩的。

综上所述，根据偶匹配可扩的定义知，循环图C2n(1，2n/3)一基数为不小于2的偶匹配M ，使得图C2n(1，2n/3)-V(M)的没有一个完美匹配。得证循环图C8(1，4)仅是1-偶匹配可扩的。

定理3 如果循环图C2n(1，4)(n＞4)是k-偶匹配可扩的，则k≤3。

证明：设循环图 C2n(1，4) 的顶点为 x0，x1，x2，…，x2n-1按逆时针顺序循环排列，且顶点下标按模2n加运算。

不失一般性，我们取循环图C2n(1，4)的一个基数为 4 的偶匹配 M={x2n-2x2n-1，x0x1，x3x4，x5x6} 。显然，图C2n(1，4)-V(M)有两个奇分支，其中一个是孤立点 x2，故图C2n(1，4)-V(M)不存在完美匹配；因 N(x2)⊂V(M)。因此，循环图 C2n(1，4)必不是4-偶匹配可扩的。

3 结语

本文主要证明了循环图C2n(1，4)是k-偶匹配可扩的上界问题，进一步我们还可以刻画它的2-偶匹配可扩性的和3-偶匹配可扩性。

［1］J.A.Bondy，U.S.R.Murty.Graph Theory with Applications［M］.London：Macmillan Press Ltd，1976.

［2］M.A.Fiol.On congruence inZnand the dimension of a multidimensional circulant［J］.Discrete Math.，1995，141（2）：123-134.

［3］Wang X M，Zhang Z K，Lin Y X.Bipartite matching extendable graphs［J］.Discrete Math，2008，308（23）：5334-5341.

［4］Wang X M，Z.K Zhang，Y.X.Lin，Degree-type conditions for bipartite extendability［J］.Ars Combinatoria，2009（90）：295-305.

［5］R T Faudree，A.Gyarfas，R.M.Schelp，and Z.Tuza，Induced matchings in bipartite graphs［J］.Disrete Math.，78（1989）：83-87.

［6］M C Golumbic，M.Lewenstein，New results on induced matchings［J］.Discrete Appl.Math.，101（2000），157-165.

［7］王秀梅.偶匹配可扩图［D］.郑州：郑州大学，2007.WANG Xiumei.Bipartite matching extendable graphs［D］.Zhengzhou：Zhengzhou University，2007.

［8］惠志昊，赵飚.哈林图的偶匹配可扩性（英文）［J］.浙江大学学报（理学版），2009，36（5）：494-496.HUI Zhihao，ZHAO Biao.Bipartite matching-extendability of Halin graphs［J］.Journal of Zhejiang University（Science Edition），2009，36（5）：494-496.

［9］惠志昊，曹欣杰.几类特殊图的匹配可扩性［J］.计算机与数字工程，2013，41（12）：1889-1995．HUI Zhihao，CAO Xinjie.Matching Extendability of Some Special Graphs［J］.Computer&Digital Engineering，2013，41（12）：1889-1995．

［10］惠志昊，张厚超，赵飚.循环图 C2n(1，(2n+1)3)的匹配可扩性［J］.数学的实践与认识，2015，45（23）：300-304.HUI Zhihao，ZHANG Houchao，ZHAO Biao.Bipartite matching-extendability of Cyclic GraphC2n(1，(2n+1)3)［J］.Mathematics in Practice and Theory，2015，45（23）：300-304.

［11］惠志昊.特殊图类的偶匹配可扩性［D］.乌鲁木齐：新疆大学，2008.HUI Zhihao.Bipartite matching-extendibility of special graphs［D］.Urumchi：Xinjiang University，2008.

k-bipartite Matching Extendability of Circulant Graph with Step Length 1 and 4

HUI Zhihao
（College of Mathematics and Statistics，Pingdingshan University，Pingdingshan 467000）

Gis said to be bipartite matching-extendable，if every bipartite matchingMofis included in a perfect matching ofG.The problem determining whether there is a bipartite matching of cardinalitykin a graphGis NP-complete.This paper shows that the k-bipartite matching extendability of circulant graphsC2n(1，4).

pefrect matching，bipartite matching，k-bipatrite matching extendable，circulant graph

O157.5

10.3969/j.issn.1672-9722.2017.11.004

Class Number O157.5

2017年5月11日，

2017年6月25日

平顶山学院青年科研基金项目（编号：2012001）；河南省科技厅重点科技攻关项目（编号：132102310126）资助。

惠志昊，男，硕士研究生，研究方向：图论与组合优化。