香蕉樹的指標和指標的顯式公式

2022-01-18 05:45:52楊利民

大理大學學報 2021年12期

楊利民

（大理大學數學與計算機學院，云南大理 671003）

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

1 定義和引理

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

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

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

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

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

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

其中A（G-V（Kij））是刪除V（Kij）和與V（Kij）相關聯的邊〔1〕。

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

引理3 假設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 假設圖G的頂點數為n并且無K3子圖，那么Hosoya指標Z（G）等于圖G的所有S（n）-因子的個數：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 假設G1，G2，…，Gt是圖G的t個分支〔4〕，那么

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

2 主要結果

2.1 香蕉樹的Hosoya指標的顯式公式假設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 假設圖G是一棵香蕉樹BT（n1，n2，…，nk），如圖1，那么它的S（n）-因子的所有個數：