循環(huán)梯狀圖的完美匹配的反強(qiáng)迫譜與盧卡斯數(shù)列

姚海元,王杰彬,王 旭

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,甘肅 蘭州 730070)

0 引言

文中研究CLn的所有完美匹配的反強(qiáng)迫數(shù),得到了CLn的反強(qiáng)迫譜及其連續(xù)性;根據(jù)完美匹配的反強(qiáng)迫數(shù)和所含的水平匹配邊數(shù)對(duì)CLn的所有完美匹配進(jìn)行分類計(jì)數(shù),得到了盧卡斯數(shù)列的兩個(gè)組合解釋.

1 預(yù)備知識(shí)

定義1梯子圖Ln是路Pn和P2的笛卡兒積,即Ln=Pn×P2,如圖1所示,將Ln水平放置,上下兩層頂點(diǎn)依次記為a1,a2,…,an和b1,b2,…,bn.循環(huán)梯狀圖CLn是圈Cn和路P2的笛卡兒積,即CLn=Cn×P2,n≥3,也就是通過梯子圖Ln添加邊a1an和b1bn得到的,如圖2所示.

圖1 梯子圖Ln

圖2 循環(huán)梯狀圖CLn

在圖Ln和圖CLn中,類似于aibi的邊稱為豎直邊,而類似于aiai+1,bibi+1,a1an,b1bn的邊稱為水平邊.設(shè)M是圖G的一個(gè)完美匹配,稱兩個(gè)M-交錯(cuò)圈是M-相容的,如果它們不交或只相交在M中的邊.A是一個(gè)由M-交錯(cuò)圈組成的集合,若A中任意兩個(gè)圈是M-相容的,則稱A是一個(gè)相容M-交錯(cuò)集.圖G的最大相容M-交錯(cuò)集的大小記為c′(G,M)或c′(M).

引理1[3]設(shè)M是圖G的任一完美匹配,則af(G,M)≥c′(M).進(jìn)一步,若圖G是平面二部圖,則af(G,M)=c′(M).

文中主要應(yīng)用引理1,將完美匹配的反強(qiáng)迫數(shù)的計(jì)算轉(zhuǎn)化為相容交錯(cuò)圈的討論.

引理2設(shè)M是Ln的一個(gè)完美匹配,若aibi∈M,2≤i≤n-1,則

af(Ln,M)=af(L(1),M1)+af(L(2),M2),

其中，Mj=M∩E(L(j)),j=1,2,L(1)和L(2)分別是Ln關(guān)于頂點(diǎn)集{a1,a2,…ai,b1,b2,…,bi}和(ai,ai+1,…,an,bi,bi+1,…,bn}導(dǎo)出的子梯子圖.

證明由于aibi∈M，所以L(1)∩L(2)={aibi},Mi,M2是L(1)和L(2)的完美匹配，且M1∩M2={aibi},Mi∪M2=M.

一方面，令A(yù)是Ln的相容M-交錯(cuò)集，Aj={C?L(j)|C∈A},j=1,2.由于aibi∈M,ai-1ai,aiai+1,bi-1bi,bibi+1?M，所以對(duì)于任意的M-交錯(cuò)圈C∈A,ai-1ai和aiai+1及bi-1bi和bibi+1不能同時(shí)在C中，如果ai-1ai∈C,則aibi,bi-1bi∈C,因此C∈A1是一個(gè)M1-交錯(cuò)圈.同理，如果aiai+1∈C,則aibi,bibi+1∈C，因此C∈A2是一個(gè)M2-交錯(cuò)圈.否則aibi?C，則ai,bi?C，所以C∈A1是一個(gè)M1-交錯(cuò)圈或C∈A2是一個(gè)M2-交錯(cuò)圈.因此A?A1∪A2.對(duì)任意的C1,C2∈A,若C1,C2∈A1(或A2)，則C1和C2是M1-相容的(或M2-相容的).否則C1∈A,C2∈A,那么Cj是Mj-相容的，j=1,2，故c′(M)≤c′(M1)+c′(M2).

另一方面，令A(yù)j是L(j)的一個(gè)相容Mj-交錯(cuò)集,j=1,2,A=A1∪A2.設(shè)C1,C2∈A是兩個(gè)任意的M-交錯(cuò)圈.若C1,C2∈Aj,則{C1,C2}是相容Mj-交錯(cuò)集，j=1,2.否則，C1∈A,C2∈A,分兩種情形討論.

情形1如果C1,C2中最多有一個(gè)圈包含邊aibi，即C1和C2不交，則C1和C2是M-相容的.

情形2如果C1∩C2={aibi}，又aibi∈M，則C1和C2是M-相容的.

因此，c′(M1)+c′(M2)≤c′(M).

綜上所述，c′(M1)+c′(M2)=c′(M).因此，由引理1可得，af(Ln,M)=af(L(1),M1)+af(L(2),M2). 】

梯子圖Ln通過分解得到的子圖L(1)和L(2)稱為L(zhǎng)n的片段.豎直匹配邊aibi∈M(2≤i≤n-1)稱為可分解豎直匹配邊,Ln的片段包含或不包含可分解豎直匹配邊稱為L(zhǎng)n的可分解片段或不可分解片段.

推論1若L(i)是Ln的一個(gè)不可分解片段,并且L(i)的完美匹配Mi包含2q條水平匹配邊和p條豎直匹配邊,則

2 循環(huán)梯狀圖的反強(qiáng)迫譜

設(shè)M是CLn的一個(gè)包含豎直匹配邊的完美匹配,不妨設(shè)a1b1∈M.假設(shè)存在一個(gè)M-交錯(cuò)圈C同時(shí)包含邊ana1,a1b1,b1b2或bnb1,b1a1,a1a2,此時(shí)稱M-交錯(cuò)圈C跨過豎直匹配邊a1b1,則這個(gè)M-交錯(cuò)圈一定經(jīng)過M中的所有p條豎直匹配邊.要使得M-交錯(cuò)圈成立,豎直匹配邊條數(shù)p一定是偶數(shù),所以這是一個(gè)長(zhǎng)為n+p的M-交錯(cuò)圈,因此只有n為偶數(shù)時(shí)才存在這樣的M-交錯(cuò)圈,并且只有兩個(gè);當(dāng)n是奇數(shù)時(shí),不存在M-交錯(cuò)圈跨過豎直匹配邊.

通過把豎直匹配邊a1b1分裂成兩條邊,如此將CLn在豎直匹配邊a1b1處分裂成梯子圖Ln+1,如圖3所示.

圖3 CLn在邊a1b1處分裂為L(zhǎng)n+1

在不引起混淆的情況下,把新分裂出來的頂點(diǎn)仍記為a1b1,且新邊a1b1仍是匹配邊,如此Ln+1比CLn多了頂點(diǎn)a1,b1和匹配邊a1b1,與CLn的完美匹配M對(duì)應(yīng)的Ln+1的完美匹配記為M′(比M多含一條豎直匹配邊),CLn中的匹配邊與非匹配邊都包含在Ln+1中.稱Ln+1的由兩條相鄰豎直匹配邊及它們之間的所有邊導(dǎo)出的子圖(即Ln+1的不可分解片段)為CLn的不可分解片段.

證明由p≥1,不妨設(shè)a1b1∈M.將CLn在豎直匹配邊a1b1處分裂成梯子圖Ln+1,與CLn的含p條豎直匹配邊的完美匹配M對(duì)應(yīng)的Ln+1的含p+1條豎直匹配邊的完美匹配記為M′,如圖3所示.此時(shí)CLn中水平匹配邊的匹配方式類似于Ln,所以M中的水平匹配邊成對(duì)出現(xiàn).下面根據(jù)n的奇偶性分兩種情況進(jìn)行討論.

情況1.當(dāng)n≥3是奇數(shù)時(shí),CLn不是一個(gè)二部圖.任取CLn的一個(gè)相容M-交錯(cuò)集A,則由全部水平邊構(gòu)成的奇圈Ca=a1a2…ana1,Cb=b1b2…bnb1?A,因而所有的M-交錯(cuò)圈必包含至少兩條豎直邊.因?yàn)槊織l豎直匹配邊共有4條鄰邊,所以同一條豎直匹配邊最多出現(xiàn)在2個(gè)A中的M-交錯(cuò)圈中,豎直單邊最多出現(xiàn)在一個(gè)A中的M-交錯(cuò)圈中,因此

其中2qi是梯子圖的各不可分解片段中相應(yīng)完美匹配的水平匹配邊條數(shù).所以

綜上所述,當(dāng)n≥3為奇數(shù)時(shí)有

情況2.當(dāng)n≥4是偶數(shù)時(shí),CLn是一個(gè)平面二部圖.設(shè)跨過a1b1的兩個(gè)M-交錯(cuò)圈為C1,C2,其中C1和C2分別是包含邊ana1,a1b1,b1b2和邊bnb1,b1a1,a1a2的M-交錯(cuò)圈.假設(shè)CLn存在一個(gè)最大的相容M-交錯(cuò)集A包含C1(則必包含C2)和與C1,C2均M-相容的由兩條水平匹配邊構(gòu)成的M-交錯(cuò)4-圈.用任意兩個(gè)相鄰豎直匹配邊及之間的水平邊構(gòu)成的M-交錯(cuò)圈替換A中的C1,C2,則由任意兩條相鄰豎直匹配邊及之間的水平邊構(gòu)成的M-交錯(cuò)圈與A中除去C1,C2的圈都是M-相容的,由此得到另外一個(gè)相容M-交錯(cuò)集A ′,所以有|A ′|≥|A|,因此存在不跨過任何豎直匹配邊的M-交錯(cuò)圈使得這個(gè)相容交錯(cuò)集達(dá)到最大.因此有c′(CLn,M)等于各不可分解片段的相容M-交錯(cuò)集大小之和,等于c′(Ln+1,M′),故由引理1有

由引理3的證明過程可知,CLn也有類似于Ln的分解定理.

定理1設(shè)M是CLn的一個(gè)完美匹配,若M包含p條豎直匹配邊,p≥1,則

af(CLn,M)=af(L(1),M1)+…+af(L(p),Mp),

其中，Mj=M∩E(L(j)),j=1,2,…,p,L(1),L(2),…,L(p)是CLn的p個(gè)不可分解片段.

推論3循環(huán)梯狀圖CLn的具有2q(

定理2

因此當(dāng)n≥3為奇數(shù)或n=4,6時(shí)CLn的反強(qiáng)迫譜是連續(xù)的,當(dāng)n≥8為偶數(shù)時(shí)CLn的反強(qiáng)迫譜是不連續(xù)的.

證明設(shè)M是CLn的具有p條豎直匹配邊的完美匹配,即M有2q=n-p條水平匹配邊.當(dāng)p=0時(shí),此時(shí)n必為偶數(shù).若水平匹配邊不成對(duì),不妨設(shè)a1a2∈M,且b1b2?M,則S={a2a3,a2b2,b2b1}是M的一個(gè)反強(qiáng)迫集,又因?yàn)锳={Ca,Cb,Cab}是一個(gè)相容M-交錯(cuò)集,其中Ca=a1a2…ana1,Cb=b1b2…bnb1,Cab=b1a1a2b2b3…an-1anbnb1,因此af(CLn,M)=3.否則,不妨設(shè)a1a2,b1b2∈M,由于n≥4是偶數(shù)且p=0,所以CLn的這個(gè)完美匹配M如圖4所示.

圖4 CLn的一個(gè)完美匹配M

推論4[6]

2)Af(CLn)=n.

3 循環(huán)梯狀圖的完美匹配和盧卡斯數(shù)列

盧卡斯數(shù)列是以l0=2,l1=1為初始值,ln=ln-1+ln-2為遞推關(guān)系的數(shù)列.

引理4[7]盧卡斯數(shù)列的第n項(xiàng)為

定理3在循環(huán)梯狀圖CLn中,記M為所有含2q條水平匹配邊的完美匹配的集合,則

若M∈M1,則刪去頂點(diǎn)a1,b1,an,bn得到梯子圖Ln-2的一個(gè)含有2q-2條水平匹配邊的完美匹配,反之亦然.由推論2有

若M∈M2,刪去邊a1an,b1bn得到梯子圖Ln的一個(gè)含有2q條水平匹配邊的完美匹配,反之亦然.由推論2有

綜上,當(dāng)n是奇數(shù)時(shí),有

當(dāng)n是偶數(shù)時(shí),設(shè)M是CLn的含有2q條水平匹配邊的完美匹配,則M包含p=n-2q條豎直匹配邊,其中0≤p≤n并且p也是偶數(shù).

當(dāng)p≥2時(shí),類似討論可得

由定理2和定理3,我們有下面的結(jié)論.

定理4

由引理4和定理3或引理4和定理4,我們可以得到下面結(jié)論.

推論5循環(huán)梯狀圖CLn的完美匹配個(gè)數(shù)

參考文獻(xiàn):

[3] LEI H,YEH Y,ZHANG H.Anti-forcing numbers of perfect matchings of graphs[J].DiscreteApplMath,2016,202:95.

[4] AFSHANI P,HATAMI H,MAHMOODIAN E S.On the spectrum of the forced matching number of graphs[J].AustralasJCombin,2004,30:147.

[5] DENG K,ZHANG H.Anti-forcing spectrum of any cata-condensed hexagonal system is continuous[J].FrontMathChina,2017,12(2):325.

[6] 梁志鵬.廣義Sierpinski圖的第一類Zagreb指標(biāo)與四角鏈的反強(qiáng)迫數(shù)[D].烏魯木齊:新疆大學(xué),2016.

[7] KOSHY,T.FibonacciandLucasNumberswithApplications[M].New York:Wiley,2001.