硼氮富勒烯圖的反強迫數

蔣曉艷,程曉勝

(惠州學院 數學系，廣東 惠州 516007)

0 引言

圖G的一個獨立邊集叫做G的一個匹配。G的完美匹配(凱庫勒結構)M是一個匹配且G的每個點都與M中的一條邊相關聯。若G的邊集S滿足G-S有唯一完美匹配，則稱S為反強迫集。包含邊數最少的反強迫集叫做極小反強迫集，其邊的數目叫做圖G的反強迫數，記作af(G) .

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

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

1 硼氮富勒烯圖的反強迫數

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

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

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

Tn的完美匹配有以下特點：

引理1[3]設M是Tn的任一完美匹配，那么M恰好包含每一層的一條橫跨邊。相反，任何一個恰好包含每一層一條橫跨邊的邊集都能擴充為Tn的唯一完美匹配。

引理2[3]設H是二部圖G的一個導出子圖，M0是H的完美匹配，且M0能擴充為G的完美匹配M。如果G-H有至多一個 1-度點，那么M0的任一子集都不是M的強迫集。

下面我們給出Tn的反強迫數。

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

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

對于任意硼氮富勒烯圖，我們給出其反強迫數的下界：

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

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

以下我們構造出所有反強迫數達到下界的的硼氮富勒烯圖。

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

證明 設G的大小為 3 的反強迫集為S={e1,e2,e3}.M為G-S的完美匹配。下面我們給出S的結構。

斷言.S中沒有獨立邊，即不與S中其它兩條邊關聯的邊。

反證，若不是，不失一般性，假設有一條獨立邊e1，則在G-S中至多有一個 1-度點，此點同時與e2,e3相關聯。由定理 2.2 知，G-S至少有兩個完美匹配，矛盾。

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

圖2 定理證明示意圖

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

參考文獻:

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