硼氮富勒烯圖的反強(qiáng)迫數(shù)

蔣曉艷,程曉勝

(惠州學(xué)院 數(shù)學(xué)系，廣東 惠州 516007)

0 引言

圖G的一個(gè)獨(dú)立邊集叫做G的一個(gè)匹配。G的完美匹配(凱庫(kù)勒結(jié)構(gòu))M是一個(gè)匹配且G的每個(gè)點(diǎn)都與M中的一條邊相關(guān)聯(lián)。若G的邊集S滿足G-S有唯一完美匹配，則稱S為反強(qiáng)迫集。包含邊數(shù)最少的反強(qiáng)迫集叫做極小反強(qiáng)迫集，其邊的數(shù)目叫做圖G的反強(qiáng)迫數(shù)，記作af(G) .

本文主要考慮硼氮富勒烯圖，它是硼氮富勒烯的分子圖。實(shí)際上，硼氮富勒烯圖是一個(gè) 3-連通，3-正則的平面圖，它的面要么是四邊形要么是六邊形，所以硼氮富勒烯圖是二部圖，并且根據(jù)歐拉公式，可以計(jì)算出它恰好有六個(gè)四邊形。

在第二部分，首先我們得到一類管狀，環(huán)邊連通度為3的硼氮富勒烯圖Tn的反強(qiáng)迫數(shù)為2(n+2) .然后，我們討論任何硼氮富勒烯圖的反強(qiáng)迫數(shù)不少于 3，并構(gòu)造出所有反強(qiáng)迫數(shù)為 3 的圖，共包含兩個(gè)。

1 硼氮富勒烯圖的反強(qiáng)迫數(shù)

我們用Tn記一類管狀硼氮富勒烯圖，其中它包含n個(gè)同心六角形層(即每一層是由三個(gè)六角形構(gòu)成的環(huán)鏈)，再在兩頭分別冠上一個(gè)由三個(gè)四邊形構(gòu)成的帽子，例如圖1中給出的是T2.值得注意的是在Tn的畫(huà)法中，最外邊的三條懸掛邊實(shí)際上關(guān)聯(lián)著同一個(gè)點(diǎn)。作為退化情況n=0,Tn，就是通常所指的立方體。記T:={Tn;n>0} .

圖1 T中的例子T2，及其層和橫跨邊的示意圖

為了方便，根據(jù)Tn的同心層，我們給出它的一個(gè)分解。定義1-層是由位于一端的三個(gè)四邊形構(gòu)成的帽子，第2-層是由與第一層相鄰的三個(gè)六邊形構(gòu)成的環(huán)鏈并去掉在1-層上度為3的三個(gè)點(diǎn)。兩個(gè)同心6-長(zhǎng)圈(非面圈，即不是某個(gè)面的邊界)之間的邊叫橫跨邊。用相同的方法我們可以定義第i-層(2≤i≤n+1) 。第(n+1)-層是Tn另一端帽子上的一個(gè)爪子(即中心一個(gè)點(diǎn)關(guān)聯(lián)這三條邊)。在每個(gè)i-層，三條橫跨邊形成一個(gè)匹配，在1-層和(n+2) -層三條橫跨邊分別與中心點(diǎn)關(guān)聯(lián)，例如見(jiàn)圖1.

Tn的完美匹配有以下特點(diǎn)：

引理1[3]設(shè)M是Tn的任一完美匹配，那么M恰好包含每一層的一條橫跨邊。相反，任何一個(gè)恰好包含每一層一條橫跨邊的邊集都能擴(kuò)充為T(mén)n的唯一完美匹配。

引理2[3]設(shè)H是二部圖G的一個(gè)導(dǎo)出子圖，M0是H的完美匹配，且M0能擴(kuò)充為G的完美匹配M。如果G-H有至多一個(gè) 1-度點(diǎn)，那么M0的任一子集都不是M的強(qiáng)迫集。

下面我們給出Tn的反強(qiáng)迫數(shù)。

定理1 若Tn∈T，則af(Tn)=2(n+2) .

證明 設(shè)S是Tn的最小強(qiáng)迫集，我們斷言則|S|≥2(n+2) 。利用反證法，假設(shè)|S|<2(n+2) 。首先對(duì)于Tn的每一層至多有兩條橫跨邊在S中，否則，Tn將被分成兩個(gè)分支，且每個(gè)分支有奇數(shù)個(gè)點(diǎn)，則Tn-S中沒(méi)有完美匹配，與S是反強(qiáng)迫集矛盾。由鴿籠原理知，至少有一層至多含有一條邊。不失一般性，假設(shè)是i-層，那么i-層中有兩條橫跨邊不在S中。而對(duì)于剩余的每一層，存在一條橫跨邊不在S中。現(xiàn)在我們選擇i-層的任從i-層中任選一條不在S中的橫跨邊，從剩余每一層中選不在S中的橫跨邊作為匹配邊，根據(jù)由引理1，我們得到兩個(gè)不包含S中邊的完美匹配，這與S是反強(qiáng)迫集矛盾，所以 |S|≥2(n+2).另外，我們可以找到一個(gè)大小恰為 2(n+2) 的反強(qiáng)迫集S0：對(duì)于i-層(1≤i≤n+2 ),任選兩條橫跨邊放在構(gòu)成S0中，則由引理1 知，Tn-S0有唯一完美匹配，且|S|=2(n+2) .由此定理得證。

對(duì)于任意硼氮富勒烯圖，我們給出其反強(qiáng)迫數(shù)的下界：

定理2 若G為任一硼氮富勒烯圖，則af(G)≥3.

證明 設(shè)S是G的反強(qiáng)迫集。反證，假設(shè)|S|≤ 2，那么G-S至多有一個(gè)1-度點(diǎn)，由引理2 知，G-S不止有一個(gè)完美匹配，矛盾，所以af(G)≥3.

以下我們構(gòu)造出所有反強(qiáng)迫數(shù)達(dá)到下界的的硼氮富勒烯圖。

定理3 設(shè)硼氮富勒烯圖G，如果af(G)=3 ，那么G同構(gòu)于B4N4或者B6N6.

證明 設(shè)G的大小為 3 的反強(qiáng)迫集為S={e1,e2,e3}.M為G-S的完美匹配。下面我們給出S的結(jié)構(gòu)。

斷言.S中沒(méi)有獨(dú)立邊，即不與S中其它兩條邊關(guān)聯(lián)的邊。

反證，若不是，不失一般性，假設(shè)有一條獨(dú)立邊e1，則在G-S中至多有一個(gè) 1-度點(diǎn)，此點(diǎn)同時(shí)與e2,e3相關(guān)聯(lián)。由定理 2.2 知，G-S至少有兩個(gè)完美匹配，矛盾。

因此，S中的邊情形有兩種。首先，e1,e2和e3關(guān)聯(lián)同一個(gè)點(diǎn)，這樣G-S中就會(huì)有孤立點(diǎn)，矛盾。第二種情況，e1,e2和e3是一條3-長(zhǎng)路上的三條邊。不妨設(shè)這條路為ae1be2ce3d，在G-S中恰好有兩個(gè)1-度點(diǎn)b和c，則邊bb1和cc1在M中。設(shè)H是由a,b,b1,c,c1,d導(dǎo)出的子圖，在G-S中，只有當(dāng)點(diǎn)a和點(diǎn)c1相鄰，點(diǎn)d和b1點(diǎn) 相鄰時(shí)，才能產(chǎn)生兩個(gè) 1-度點(diǎn)a和d，否則G-S中沒(méi)有1-度點(diǎn)。如此邊aa1和邊dd1在M中。設(shè)H1是由點(diǎn)集V(H)∪{a1,d1} 所導(dǎo)出的子圖。如果在G-H1中沒(méi)有其它點(diǎn)，則連接邊a1，b1,c1，d1,a1,d1就會(huì)得到圖B4N4,見(jiàn)圖2 (a)。

圖2 定理證明示意圖

若還有其它點(diǎn)，只有當(dāng)點(diǎn)w1與點(diǎn)a1，c1相鄰，w2與點(diǎn)b1，d1相鄰時(shí)為 1-度點(diǎn)，那么邊w1w3和w2w4在M中。由硼氮富勒烯圖的定義，則一定有邊連結(jié)點(diǎn)w3和點(diǎn)w4，否則將產(chǎn)生 2-邊割。至此我們得到B6N6，見(jiàn)圖2 (b)。

參考文獻(xiàn):

[3]Jiang X Y,Zhang H P. On forcing matching number of Boron-nitrogen fullerene graphs[J].Discrete Appl Math, 2011, 159:1581～1593.