3正則的ID-因子臨界圖

梁彩霞

（肇慶學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 肇慶 526061）

3正則的ID-因子臨界圖

梁彩霞

（肇慶學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 肇慶 526061）

如果對(duì)于G中任意和 ||V(G)有相同奇偶性的獨(dú)立集I,G-I有完美匹配,則稱(chēng)圖G是ID-因子臨界圖，給出了3-正則的ID-因子臨界圖的刻畫(huà).

完美匹配;3-正則;獨(dú)立集;ID-因子臨界圖

1 概述

文中未定義的術(shù)語(yǔ)和概念參見(jiàn)文獻(xiàn)[1].本文涉及的圖為有限、無(wú)向的簡(jiǎn)單圖.令S為圖G的頂點(diǎn)的子集，G-S的奇分支數(shù)記為o(G-S).設(shè)u是G中任一頂點(diǎn)，記意2點(diǎn)不相鄰,則稱(chēng)I為獨(dú)立集.若G的所有頂點(diǎn)的度都等于k,則稱(chēng)G為k-正則圖.圖G不包含K1,3為導(dǎo)出子圖，稱(chēng)之為無(wú)爪圖.對(duì)邊集M?E(G),如果G的任意頂點(diǎn)至多與M中的1條邊關(guān)聯(lián),則稱(chēng)M是G的匹配.稱(chēng)覆蓋所有頂點(diǎn)的匹配為完美匹配.

因子理論一直是圖論中的重要研究領(lǐng)域[2],對(duì)因子理論的研究最早可以追溯到1個(gè)世紀(jì)以前.1891年，Peterson[3]指出：2-邊連通的3-正則圖有1-因子，這被認(rèn)為是現(xiàn)代因子理論研究的開(kāi)始.1947年，Tutte[4]給出一個(gè)普通圖G有1-因子的充要條件,該結(jié)論是因子理論中最基本的理論,奠定了因子理論的基礎(chǔ).1952年，Tutte[5]又給出圖G有 f-因子的充要條件；1970年，Lovász[6]得到一個(gè)圖G有(g,f)-因子的充要條件.從那時(shí)起，關(guān)于圖的因子理論的結(jié)果不斷涌現(xiàn).如果對(duì)于G中任意頂點(diǎn)u,G-u有完美匹配(即1-因子)，則稱(chēng)G是因子臨界圖.在文獻(xiàn)[7]中,原晉江把因子臨界圖的概念推廣為獨(dú)立集可削去的因子臨界圖.如果對(duì)于G中任意和 ||V(G)有相同奇偶性的獨(dú)立集I,G-I有完美匹配，則稱(chēng)圖G是獨(dú)立集可消去的因子臨界圖(簡(jiǎn)稱(chēng)為ID-因子臨界圖).ID-因子臨界圖的研究成果可參見(jiàn)文獻(xiàn)[8-12].本文刻畫(huà)了3-正則的ID-因子臨界圖，進(jìn)一步完善了圖的因子理論.

2 主要結(jié)果與證明

引理1[4]若圖G有完美匹配,當(dāng)且僅當(dāng)對(duì)任意的S?V(G),o(G-S)≤ ||S.

由圖的正則性，在以下的討論中G中頂點(diǎn)的個(gè)數(shù)為偶數(shù).

定理1 無(wú)爪的3-正則ID-因子臨界圖只有圖1中的G1,G2及G3.

證 易驗(yàn)證G1,G2及G3都是無(wú)爪的3-正則ID-因子臨界圖.設(shè)G是無(wú)爪的3-正則ID-因子臨界圖，下面證明G同構(gòu)于G1,G2或G3.設(shè)u是G中任一頂點(diǎn)，由G是無(wú)爪圖知1≤f(u)≤3.

情形1 f(u)=1.

在該情形下，2≤ ||N(2)(u)≤4.不失一般性，不妨設(shè)x1與x2相鄰，由G的正則性知x3與N(2)(u)中的2個(gè)頂點(diǎn)，不妨設(shè)為y1與y2相鄰，且由G無(wú)爪知y1與y2相鄰.

當(dāng) ||N(2)(u)=2時(shí)，由G是3-正則的知xi(i=1,2)與且僅與y1和y2中之一相鄰，yi(i=1,2)與且僅與x1和x2中之一相鄰，此時(shí)G?G1.

當(dāng) ||N(2)(u)=3時(shí)，不失一般性，設(shè)另有y3∈N(2)(u),且y3與x1相鄰.若x2也與y3相鄰，取I={ } x3,y3，則G-I含有奇分支，與引理1矛盾，從而x2與y3不相鄰.不妨設(shè)x2與y2相鄰，則有y1與y3必不相鄰，否則圖G含有以y3為中心的爪.從而I={ } y1,y3是G中的獨(dú)立集,且G-I含有奇分支，矛盾.

當(dāng) ||N(2)(u)=4時(shí),不失一般性，設(shè)另有y3,y4∈N(2)(u),且y3與x1相鄰，y4與x2相鄰.斷言1 y3與y1和y2不相鄰，y4與y1和y2不相鄰.

若y3與y1相鄰，則y3與y2也相鄰，否則含爪.由G是3-正則的，有取含有奇分支,矛盾，從而有y3與y1不相鄰，類(lèi)似地有y3與y2不相鄰，y4與y1,y2不相鄰.

斷言2 y3與y4不相鄰.

假設(shè)y3與y4相鄰，且y3與z∈N(3)(u)相鄰.若y4與z相鄰，取I={ } z,x3,G-I含有奇分支,矛盾；若y4與z不相鄰，取

否則，設(shè)w∈N(4)(u),由斷言2知是圖G中的獨(dú)立集，但G-I含有奇分支,矛盾.

當(dāng) |N(3)(u)|=6時(shí)，由G的正則性知與且僅與N(2)(u)中的1個(gè)頂點(diǎn)相鄰.不妨設(shè)y1與z1相鄰，取獨(dú)立集則G-I含有奇分支,矛盾．

情形2 f(u)=2.

不失一般性，設(shè)x1,x2均與x3相鄰.在這種情形下

情形3 f(u)=3.

顯然，此時(shí)G?K4=G3.

定理2 含爪的3-正則ID-因子臨界圖只有圖2中的G4,G5,G6,G7,G8.

證 易驗(yàn)證圖2中的Gi(i=4,5,6,7,8)是含爪的3-正則ID-因子臨界圖.設(shè)G是含爪3-正則ID-因子臨界圖，下證明G同構(gòu)于圖2中的Gi(i=4,5,6,7或8).不妨設(shè)G′是G中的1個(gè)爪,其中V(G′)={ } u,x1,x2,x3,u是該爪的中心.

由定理1和定理2顯然有以下推論1.

推論1 3-正則的ID-因子臨界圖有且只有8個(gè)，見(jiàn)圖1和圖2.

圖1 無(wú)爪的3-正則ID-因子臨界圖

[1] BONDY JA,MURTY S R.Graph theory with applications[M].London:Macmillan Press Ltd,1976.

[2] 于青林,劉桂真.圖的因子和匹配可擴(kuò)性[M].北京：高等教育出版社,2010.

[3] PETERSEN J.Die theorie der regul?ren[J].AetaMath,1891,15:193-220.

[4] TUTTE W T.The factorizations of linear graphs[J].London Math Soc,1947,22:107-111.

[5] TUTTE W T.The factors of graphs[J].Can J Math,1952(4):314-328.

[6] LOVáSZ.Subgraphs with prescribed valancies[J].J Comb Theory Ser B,1970(9):391-416.

[7] YUAN Jinjiang.Independent-set-deletable factor-critical power graphs[J].Acta Mathematica Scientia,2006,26B(4):577-584.

[8] LIU Yan.The degree conditions of ID-factor-critical graphs[J].SouthestAsian Bulletin of Mathematics,2003,27:641-648.

[9] LIANG Caixia,LIU Yan.The degree sum conditions of ID-factor-critical Graphs[J].Chinese Journal of Engineering Mathematics,2006,23:169-174.

[10] 馬芳,劉巖.獨(dú)立集可削去的因子臨界圖和無(wú)爪的獨(dú)立集可削去因子臨界圖的度條件[J].華南師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2008(2):29-33.

[11] MA Fang,LIU Yan.ID-factor-critical and claw-free graphs of diameter 2[J].Southeast Asian Bulletin of Math，2009,33:879-883.

[12] LIANG Caixia,LIU Yan.ID-factor-critical claw-free Graphs[J].Pacific Journal ofApplied Mathematics,2013,4(5):253-258.

3-Regular ID-Factor-Critical Graphs

LIANG Caixia

(School of Mathematics and Statistics,Zhaoqing University,Zhaoqing,Guangdong 526061,China)

:Gis ID-factor-critical if for every independent setIofGwhich has the same parity with ||V(G), G-Ihas a perfect matching.The 3-regular ID-factor-critical Graphs are characterized.

:perfect matching;3-regular;independent set;ID-factor-critical

O157.5

A

1009-8445（2017）02-0008-04

（責(zé)任編輯：陳 靜）

2016-07-01

廣東省自然科學(xué)基金資助項(xiàng)目（2014A030310277）；肇慶學(xué)院教學(xué)質(zhì)量工程項(xiàng)目（80111323）

梁彩霞（1978-），女，廣東茂名人，肇慶學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院講師，碩士.