步長為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）資助。

惠志昊，男，碩士研究生，研究方向：圖論與組合優化。