步長為1和4的循環(huán)圖的k-偶匹配可擴(kuò)性?

惠志昊

（平頂山學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院 平頂山 467000）

步長為1和4的循環(huán)圖的k-偶匹配可擴(kuò)性?

惠志昊

（平頂山學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院 平頂山 467000）

稱圖G是偶匹配可擴(kuò)的，是指G的每一個(gè)偶匹配M都可以擴(kuò)充為G的一個(gè)完美匹配。判定圖是否含有基數(shù)為k的偶匹配是NP-困難問題，該文主要刻畫了循環(huán)圖C2n(1，4)的k-偶匹配可擴(kuò)性。

完美匹配；偶匹配可擴(kuò)；k-偶匹配可擴(kuò)；循環(huán)圖

1 引言

設(shè)圖G是一簡單的且有完美匹配的連通圖。稱圖G是k-偶匹配可擴(kuò)的，是指G的每一個(gè)基數(shù)不大于k(1≤k≤(|V(G)|-2)2)的偶匹配M 都可以擴(kuò)充為G的一個(gè)完美匹配。本文中沒有加以說明的概念和術(shù)語可參考［1］，關(guān)于圖的匹配可擴(kuò)性和k-偶匹配可擴(kuò)性已經(jīng)有很多結(jié)論［3～11］。在文獻(xiàn)［7］中證明了判定圖G是否含有基數(shù)是k的偶匹配是NP-困難問題；判定圖G是否是偶匹配可擴(kuò)的是co-NP-困難問題。本文主要根據(jù)圖的k-偶匹配可擴(kuò)性完全刻畫了循環(huán)圖C2n(1，4)的偶匹配可擴(kuò)性。這對(duì)我們進(jìn)一步判定偶匹配可擴(kuò)圖有很重要的意義。

定義1 對(duì)一個(gè)有 2n 個(gè)頂點(diǎn) x0，x1，x2，…， x2n-1的圖G，如果 xixj是圖G的邊，當(dāng)且僅當(dāng)i-j≡±1(mod2n)，或者 i-j≡±k(mod2n)，則稱圖 G為步長為1和 k 的循環(huán)圖，記為 C2n(1，k)［2］。

令 Zn為模 n的剩余類加群，即Zn={0，1，2，…，n-1}運(yùn)算取模 n的加所構(gòu)成的群。若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的最大整數(shù)。

定義 2［2］對(duì)上述 Zn，S ，若圖 G=(V，E)滿足點(diǎn)集V(G)=Zn，邊集 E(G)={(i，j)|j-i∈S}，則稱 G為Zn上關(guān)于特征集S的循環(huán)圖，記為Cn(j1，j2，j3，…，jr) ，其 中 j1＜j2＜j3＜…＜jr，并 稱j1，j2，j3，…，jr為生成元。

引理1［1］（Tutte定理） 圖G中存在完美匹配，當(dāng)且僅當(dāng)對(duì)于任意的S?V(G)，ο(G-S)≤ ||S，其中ο(G)表示G的奇分支數(shù)。

引理2［3］圖G是偶匹配可擴(kuò)的，當(dāng)且僅當(dāng)對(duì)于 G的任意偶匹配 M 的 S?V(G)V(M)，有ο(G-V(M)-S)≤ ||S 。

引理3［3］圖G是偶匹配可擴(kuò)的，當(dāng)且僅當(dāng)對(duì)任意的 S?V(G)，ο(G-S)≤ ||S-2mb(S)。其中mb(S)表示G[S]中最大偶匹配的基數(shù)。

2 循環(huán)圖C2n(1，4)的k-偶匹配可擴(kuò)性

定理1 循環(huán)圖Cn(1，n 2)可分解為一個(gè)1-因子和2-因子的邊不重的并。

定理2 循環(huán)圖C8(1，4)僅是1-偶匹配可擴(kuò)圖。

證明：設(shè)循環(huán)圖 C8(1，4)的頂點(diǎn)為 x0，x1，x2，…，x7按逆時(shí)針順序循環(huán)排列，且頂點(diǎn)下標(biāo)按模8加運(yùn)算。

如果取圖C8(1，4)的一基數(shù)為 3偶匹配M={x0x1，x3，x4，x5，x6} ，則 C8(1，4)-V(M)有兩個(gè)孤立點(diǎn)x2和x7。因此，C8(1，4)不是偶匹配可擴(kuò)圖。

任取循環(huán)圖C8(1，4)的一偶匹配M ，我們根據(jù)它的基數(shù)判定該圖的k-偶匹配可擴(kuò)性：

設(shè)M 是循環(huán)圖C8(1，4)的一基數(shù)為1的偶匹配，記為M={xixj}。由定理1知循環(huán)圖C8(1，4)可分解為一個(gè)1-因子和2-因子的邊不重的并，記N={x0x4，x1x5，x2x6，x3x7} ，C8=x0x1x2…x7x0。 易知，M?N或者M(jìn)?E(C8)。從而，知圖C8(1，4)的偶匹配M可以擴(kuò)充為它的一個(gè)完美匹配。因此，循環(huán)圖C8(1，4)是1-偶匹配可擴(kuò)的。

設(shè)M 是循環(huán)圖C8(1，4)的一基數(shù)為2的偶匹配，記為M={xixj，xsxt}。若M 中的元素僅是步長為1的邊，令M={ }xixi+1，xjxj+1。當(dāng) j=i+3時(shí)，則C8(1，4)-V(M)同構(gòu)于 K1，3，故圖 C8(1，4)-V(M)不存在完美匹配。因此，C8(1，4)必不是2-偶匹配可擴(kuò)的。

綜上所述，根據(jù)偶匹配可擴(kuò)的定義知，循環(huán)圖C2n(1，2n/3)一基數(shù)為不小于2的偶匹配M ，使得圖C2n(1，2n/3)-V(M)的沒有一個(gè)完美匹配。得證循環(huán)圖C8(1，4)僅是1-偶匹配可擴(kuò)的。

定理3 如果循環(huán)圖C2n(1，4)(n＞4)是k-偶匹配可擴(kuò)的，則k≤3。

證明：設(shè)循環(huán)圖 C2n(1，4) 的頂點(diǎn)為 x0，x1，x2，…，x2n-1按逆時(shí)針順序循環(huán)排列，且頂點(diǎn)下標(biāo)按模2n加運(yùn)算。

不失一般性，我們?nèi)⊙h(huán)圖C2n(1，4)的一個(gè)基數(shù)為 4 的偶匹配 M={x2n-2x2n-1，x0x1，x3x4，x5x6} 。顯然，圖C2n(1，4)-V(M)有兩個(gè)奇分支，其中一個(gè)是孤立點(diǎn) x2，故圖C2n(1，4)-V(M)不存在完美匹配；因 N(x2)?V(M)。因此，循環(huán)圖 C2n(1，4)必不是4-偶匹配可擴(kuò)的。

3 結(jié)語

本文主要證明了循環(huán)圖C2n(1，4)是k-偶匹配可擴(kuò)的上界問題，進(jìn)一步我們還可以刻畫它的2-偶匹配可擴(kuò)性的和3-偶匹配可擴(kuò)性。

［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］王秀梅.偶匹配可擴(kuò)圖［D］.鄭州：鄭州大學(xué)，2007.WANG Xiumei.Bipartite matching extendable graphs［D］.Zhengzhou：Zhengzhou University，2007.

［8］惠志昊，趙飚.哈林圖的偶匹配可擴(kuò)性（英文）［J］.浙江大學(xué)學(xué)報(bào)（理學(xué)版），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］惠志昊，曹欣杰.幾類特殊圖的匹配可擴(kuò)性［J］.計(jì)算機(jī)與數(shù)字工程，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］惠志昊，張厚超，趙飚.循環(huán)圖 C2n(1，(2n+1)3)的匹配可擴(kuò)性［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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］惠志昊.特殊圖類的偶匹配可擴(kuò)性［D］.烏魯木齊：新疆大學(xué)，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日

平頂山學(xué)院青年科研基金項(xiàng)目（編號(hào)：2012001）；河南省科技廳重點(diǎn)科技攻關(guān)項(xiàng)目（編號(hào)：132102310126）資助。

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