多邊形鏈的完美匹配數(shù)與Caterpillar樹(shù)的Hosoya指標(biāo)之間關(guān)系

楊 秀，趙 飚

（新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830046）

1 引言

1971年，日本化學(xué)家Hosoya[1]首次提出一種拓?fù)渲笜?biāo)，用Z來(lái)表示.后人稱(chēng)之為Hosoya指標(biāo)，它是研究苯碳?xì)浠衔锏姆肿咏Y(jié)構(gòu)與其物理化學(xué)性質(zhì)之間聯(lián)系的一類(lèi)重要參數(shù),并且他證明了該指標(biāo)與苯碳?xì)浠衔锏奈锢砘瘜W(xué)性質(zhì),尤其是與它的沸點(diǎn)有緊密聯(lián)系.

設(shè)G（E，V）是一個(gè)化學(xué)圖,則圖G的Hosoya指標(biāo)定義為G的所有匹配的數(shù)目之和，記作Z（G）,即

其中，m(G,k)為圖G中含有k條邊的匹配的數(shù)目.為計(jì)算方便，我們規(guī)定m(G,0)=1.

我們先回顧一些基本概念，六邊形系統(tǒng)是一個(gè)有限的2-連通平面圖，并且它的每一個(gè)內(nèi)部面都為六邊形；六邊形鏈?zhǔn)沁@樣一個(gè)六邊形系統(tǒng)，它的每一個(gè)六邊形都至多有兩個(gè)相鄰的六邊形.

同樣的，八邊形系統(tǒng)是一個(gè)有限的2-連通平面圖，并且它的每一個(gè)內(nèi)部面都為八邊形；八邊形鏈?zhǔn)沁@樣一個(gè)八邊形系統(tǒng)，它的每一個(gè)八邊形都至多有兩個(gè)相鄰的八邊形，如圖1所示.

稱(chēng)M哿E(G)是G的匹配,如果M中的任意兩條邊在G中都不相鄰.稱(chēng)M是G的完美匹配,如果V(M)=V(G).本文中的Kekulé 結(jié)構(gòu)也就是圖論中所定義的完美匹配.

近年來(lái)，關(guān)于六邊形鏈的Hosoya指標(biāo)已有許多重要結(jié)果.Gutman[2]證明了在所有六邊形鏈中，直六邊形鏈?zhǔn)蔷哂袠O小Hosoya指標(biāo)的唯一六邊形鏈；張.[3]證明了Zig-zag六邊形鏈?zhǔn)蔷哂袠O大Hosoya指標(biāo)的唯一六邊形鏈；Gutman[4]證明了六邊形鏈的六邊形多項(xiàng)式BG(X)與Caterpillar樹(shù)的特征多項(xiàng)式之間有緊密聯(lián)系，作為一個(gè)推論推出，存在一類(lèi)Caterpillar樹(shù)使得六邊形鏈的Kekulé 結(jié)構(gòu)的數(shù)目與Caterpillar樹(shù)的Hosoya指標(biāo)相等；沿這條主線(xiàn)，Hosoya和Gutman[5]研究了六邊形鏈的Kekulé 結(jié)構(gòu)數(shù)目與一些看似無(wú)關(guān)的概念之間的聯(lián)系，如路的匹配數(shù)，同時(shí)也給出了六邊形鏈H的Kekulé 結(jié)構(gòu)數(shù)目的具體表達(dá)公式；2012年，李樹(shù)立[6]證明了存在與四邊形鏈相對(duì)應(yīng)的Caterpillar樹(shù)使得它的Hosoya指標(biāo)與四邊形鏈的Kekulé 結(jié)構(gòu)數(shù)目相等.本文作者在上一篇文章中證明了存在與八邊形鏈相對(duì)應(yīng)的Caterpillar樹(shù)使得它的Hosoya指標(biāo)與八邊形鏈的Kekulé 結(jié)構(gòu)數(shù)目相等.

在這篇文章中，主要通過(guò)一種新的變換方法，證明對(duì)于任意八邊形鏈存在與之相對(duì)應(yīng)的Caterpillar樹(shù)，使得Caterpillar樹(shù)的Hosoya指標(biāo)與八邊形鏈的Kekulé 結(jié)構(gòu)數(shù)目相等，并給出Kekulé 結(jié)構(gòu)數(shù)目的表達(dá)公式.

圖1

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

在證明主要結(jié)果之前，我們先了解一些證明中用到的概念.

設(shè)Q為含有h個(gè)八邊形的八邊形鏈，則其中的八邊形有以下四種聯(lián)接方式：每個(gè)八邊形鏈都有兩個(gè)起止八邊形l1,而其他的八邊形為直線(xiàn)型的l2，拐角型的a或s.如圖2中所示.

由于本質(zhì)上l1和l2并無(wú)分別，故均用l來(lái)表示.因此，含有h個(gè)八邊形的八邊形鏈Q(jìng)可以用一系列關(guān)于1,a和s的字母序列來(lái)表示，稱(chēng)此序列為las-序列.例如：圖1中的八邊形鏈所對(duì)應(yīng)的las-序列為：llslaslll,我們將ll和lll分別簡(jiǎn)記為l2和l3等等，則圖1中八邊形鏈的las-序列可簡(jiǎn)記為：l2sl1al0sl3.八邊形鏈的las-序列的一般形式為：lt1Plt2Plt3…ltn-1Pltn，其中，P為拐角八邊形s或a.

圖2

在六邊形鏈中，六邊形的聯(lián)接主要有三種聯(lián)接方式：起止六邊形L1，直線(xiàn)型六邊形L2,拐角六邊形A，如圖3所示.從而，對(duì)于任意一個(gè)六邊形鏈H，都存在一個(gè)與之相對(duì)應(yīng)的LA-序列，且它的一般形式為：Lt1ALt2A…Ltn-1ALtn.

圖3

下面我們介紹一類(lèi)Caterpillar樹(shù)：設(shè)Pn為n個(gè)頂點(diǎn)的路，樹(shù)T(t1,t2,…,tn)為將tj個(gè)頂點(diǎn)聯(lián)接到Pn上第j(j=1,2,…，n)個(gè)點(diǎn)得到的圖.例如，T4和T(2,1,0,0,1)如圖4所示.

下面我們介紹八邊形鏈中一種新的變換：

2.1 變換C

對(duì)于八邊形鏈中任意一個(gè)八邊形(a1,a2,a3,…,a8),都存在兩個(gè)度數(shù)為2的相鄰的頂點(diǎn)ai,ai+1，去掉以ai,ai+1及它們相關(guān)聯(lián)的邊，再連接ai-1與ai+2，得到六邊形(a1,…,ai-1,ai+2,…,a8).稱(chēng)此為變換C，我們對(duì)每一個(gè)八邊形都實(shí)行這種變換則得到一個(gè)新的六邊形鏈.

引理2.2[4]對(duì)于任意六邊形鏈H，H的LA-序列為L(zhǎng)t1ALt2A…Ltn-1ALtn，則H中的Kekulé 結(jié)構(gòu)總數(shù)與Caterpillar樹(shù)T(t1,t2,…,tn)的Hosoya指標(biāo)相等.

引理2.3[5]對(duì)于任意LA-序列為L(zhǎng)t1ALt2A…Ltn-1ALtn的六邊形鏈H，有

其中，M為路Pn的一個(gè)匹配，M(Pn)為路Pn的所有匹配的集合，從而有|M(Pn)|=Z(Pn).

3 主要結(jié)果的證明

定理3.1 對(duì)八邊形鏈Q(jìng)的每個(gè)八邊形施行C變換得到六邊形鏈H，則有Q的完美匹配數(shù)與H的完美匹配數(shù)相等，即K(Q)=K(H).

證明 設(shè)八邊形鏈Q(jìng)的lax-序列為…lt1Piltn+1…，其中Pi(i=1,2,…,n)為Q中的第i個(gè)八邊形，Pi中四個(gè)相繼的頂點(diǎn)記為wi,xi,yi,zi，其中，d(xi)=d(yi)=2，則對(duì)這四個(gè)點(diǎn)施行C變換，即去掉Pi的頂點(diǎn)xi與yi以及邊xiyi,wixi,yizi，再連接wizi.對(duì)于Q中任意一個(gè)完美匹配M，若xiyi∈M，則對(duì)應(yīng)六邊形鏈H中的不包含wizi邊的完美匹配；若xiyi埸M，則對(duì)應(yīng)H中包含邊wizi的完美匹配.從而得到，Q中完美匹配的數(shù)目與H中完美匹配數(shù)目的相等.

定理3.2 對(duì)于lsa-序列為lt1Plt2Plt3…ltn-1Pltn，其中P為拐角八邊形a或s，存在與之相對(duì)應(yīng)的Caterpillar樹(shù)T(k1,k2,…,kq)，其中q-1為八邊形鏈中l(wèi)2與a的個(gè)數(shù)之和.

證明 不難看出，我們?cè)趯?duì)八邊形鏈Q(jìng)施C 變換的過(guò)程中，有如下對(duì)應(yīng)關(guān)系：l1→L;l2→A;a→A;s→L，這樣我們得到一個(gè)與八邊形鏈相對(duì)應(yīng)的LA-序列，且在這個(gè)序列中A的個(gè)數(shù)為lsa-序列中l(wèi)個(gè)數(shù)與a的個(gè)數(shù)之和減2，定理得證.

至此，我們證明了對(duì)于任意的八邊形鏈A，我們很快能找到與之相對(duì)應(yīng)的Caterpillar樹(shù)T(k1,k2,…,kq)使得K(Q)=Z(T(k1,k2,…,kq)).

同理，對(duì)于任意n邊形鏈Q(jìng)(n≥8且n為偶數(shù))，我們可反復(fù)使用C變換可得到與這個(gè)多邊形鏈對(duì)應(yīng)的一條六邊形鏈P，且在這個(gè)變換過(guò)程中Kekulé 的結(jié)構(gòu)數(shù)目不變，再利用引理2.2可得到存在Caterpillar樹(shù)T(k1,k2,…,kq)，并且n邊形鏈中Kekulé 的結(jié)構(gòu)數(shù)目與T(k1,k2,…,kq)的Hosoya指標(biāo)相等，即K(Q)=Z(T(k1,k2,…,kq)).

〔1〕Hosoya H.Topological index. A newly proposed quantity characterizing the topo-logical nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn.44 (1971) 2332-2339.

〔2〕Gutman, I.: Extremal hexagonal chains. J. Math. Chem.12 (1–4), 197–210 (1993). Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991).

〔3〕Zhang, L.-Z.: The proof of Gutman’s conjectures concerning extremal hexagonal chains. J. Syst. Sci. Math.Sci. 18(4), 460–465 (1998).

〔4〕I.Gutman, Topological properties of benzenoid systems,Theor.Chim.Acta. 45 (1977)307-315.

〔5〕H. Hosoya, I. Gutman, Kekulé structures of hexagonal chains -some unusual connections, Math. Chem. 44(2008) 559-68.

〔6〕S.L.Li, W.G.Yan,Kekulé structures of polyomino chains and the Hosoya index of caterpillar trees, Discrete Math. 312(2012) 2397-2400.