香蕉树的指标和指标的显式公式

2022-01-18杨利民

大理大学学报 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）-因子的所有个数：