楊利民

（大理大學(xué)數(shù)學(xué)與計算機學(xué)院，云南大理 671003）

在文獻(xiàn)〔1〕中，通過覆蓋方法推出S（n）-因子的計數(shù)的分支分析法，分支分析法實際是一種遞歸計數(shù)方法，只不過是以完全圖作為分支的計數(shù)方法。在文獻(xiàn)〔2〕中，利用分支分析法，獲得四葉樹的Hosoya指標(biāo)。在文獻(xiàn)〔3-4〕中，得到Merrifield-Simmons指標(biāo)的遞歸計數(shù)方法，它是第二種分支分析法。在這篇論文中，我們分別采用兩種分支分析法〔1，4〕，獲得香蕉樹的Hosoya指標(biāo)和Merrifield-Simmons指標(biāo)的顯式公式，它們是化學(xué)圖論中兩個重要的拓?fù)鋮?shù)，對組合化學(xué)具有重要價值和實際意義〔5-7〕。

1 定義和引理

1.1 定義定義1 令S（n）=｛Ki:1≤i≤n｝，n≥1，并且Ki是有i個頂點的完全圖，如果M是圖G的一個子圖，且M的任意分支都同構(gòu)于S（n）=｛Ki:1≤i≤n｝的某一元素，那么M叫做圖G的一個S（n）-子圖，如果M是圖G的一個生成子圖，那么M叫做圖G的一個S（n）-因子〔1〕。

恰有k個分支的S（n）-因子的個數(shù)記為N（G，k），S（n）-因子的所有個數(shù)記為A（G）。

定義2 圖G的所有k-匹配個數(shù)，包括空集，稱作Hosoya指標(biāo)。Hosoya指標(biāo)用Z（G）表示〔2〕。

定義3 圖G的所有獨立集的個數(shù)，包括空集，稱作Merrifield-Simmons指標(biāo)，用i（G）表示〔3〕。

1.2 基本引理第一種分支分析法如下：

引理1 對于圖G的給定一點P，如果過給定點P的完全圖是Ki1，Ki2，…，Kir，ij?［1，n］，1≤j≤r，n是G的頂點數(shù)，于是G的所有S（n）=｛Ki:1≤i≤n｝-因子個數(shù)：

其中A（G-V（Kij））是刪除V（Kij）和與V（Kij）相關(guān)聯(lián)的邊〔1〕。

引理2 假設(shè)G1，G2，...，Gt是圖G的t個分支〔1〕，那么

引理3 假設(shè)K1，n是n+1個點的星形圖，那么A（K1，n）=n+1。

證明：因為K1，n是n+1個點的星形圖，所以

從而A（K1，n）=N（K1，n，1）+N（K1，n，2）+…+N（K1，n，n-1）+N（K1，n，n）+N（K1，n，n+1）=0+0+…+0+n+1=n+1。

引理4 假設(shè)圖G的頂點數(shù)為n并且無K3子圖，那么Hosoya指標(biāo)Z（G）等于圖G的所有S（n）-因子的個數(shù)：Z（G）=A（G）〔2〕。

第二種分支分析法如下：

引理5 如果v?V（G），那么i（G）=i（G-v）+i（G-NG［v］），其中v在G中的鄰域記為NG（v），并且NG［v］=v∪NG（v）〔4〕。

引理6 假設(shè)G1，G2，…，Gt是圖G的t個分支〔4〕，那么

引理7 假設(shè)K1，n是n+1個頂點的星形圖，那么i（K1，n）=2n+1〔4〕。

2 主要結(jié)果

2.1 香蕉樹的Hosoya指標(biāo)的顯式公式假設(shè)K1，n1，K1，n2，…，K1，nk是一族互不相交的星形圖，V（K1，ni）=｛ci，ai1，ai2，…，aini｝，并且deg（ci）=ni，1≤i≤k。一棵香蕉樹BT（n1，n2，...，nk）是這樣一棵樹，通過增加一個新的頂點o，并把它連接到a11，a21，…，ak1上，所得到的樹〔8〕。

定理1 假設(shè)圖G是一棵香蕉樹BT（n1，n2，…，nk），如圖1，那么它的S（n）-因子的所有個數(shù)：

圖1 香蕉樹BT（n1，n2，...，nk）

證明：因為G是一棵香蕉樹BT（n1，n2，...，nk），它是特殊的一棵樹，所以香蕉樹無K3子圖，它也就沒有K4，K5，…，Kn子圖。利用第一種分支分析法，對固定點o進(jìn)行分析，過o點的完全圖只有點K1和k個K2，即點o和邊oa11，oa21，…，oak1。討論分2種情況：

情況一 過o點的完全圖為K1，作為一個分支，則S（n）-因子個數(shù)如下：

根據(jù)引理2得到

根據(jù)引理3就有

情況二 過o點的完全圖為oa11，oa21，...，oak1，這k個完全圖K2是對稱的，K2作為兩個點的完全分支，則

綜上所述，根據(jù)引理1，于是

以致有

定理2 如果圖G是一棵香蕉樹BT（n1，n2，…，nk），則它的Hosoya指標(biāo)

證明：因為G是一棵香蕉樹BT（n1，n2，…，nk），它是特殊的一棵樹，所以香蕉樹無K3子圖。

根據(jù)引理4，于是

再根據(jù)定理1，得到

從而有

推論1 如果圖G是一棵香蕉樹BT（n，n，…，n），n的個數(shù)是k，則它的Hosoya指標(biāo)

證明：結(jié)論來自定理2，證明略。

例1 假設(shè)圖G是香蕉樹BT（3，3，3，3），如圖2，則它的Hosoya指標(biāo)

圖2 香蕉樹BT（3，3，3，3）

Z（BT（3，3，3，3））=1 024。

證明：因為圖G是香蕉樹BT（3，3，3，3），所以n=3，k=4。

根據(jù)推論1，于是

2.2 香蕉樹的Merrifield-Simmons指標(biāo)的顯式公式

定理3 如果圖G是一棵香蕉樹BT（n1，n2，…，nk），則它的Merrifield-Simmons指標(biāo)

證明：利用第二種分支分析法，在圖1中，對o點進(jìn)行分析，根據(jù)引理5，于是

根據(jù)引理6，我們有

通過引理7，從而

推論2 如果圖G是一棵香蕉樹BT（n，n，…，n），n的個數(shù)是k，則它的Merrifield-Simmons指標(biāo)

證明：結(jié)果來自定理3，證明略。

例2 假設(shè)圖G是香蕉樹BT（3，3，3，3），如圖2，則它的Merrifield-Simmons指標(biāo)

證明：因為圖G是香蕉樹BT（3，3，3，3），所以n=3，k=4。

根據(jù)推論2得到

本文分別采用兩種分支分析法，得到香蕉樹的Hosoya指標(biāo)和Merrifield-Simmons指標(biāo)的顯式公式，這些結(jié)果對化學(xué)圖論是有價值和實際意義的。