杨 利 民， 段 丽 燕， 王 天 明

( 1.大理大学 数学与计算机学院, 云南 大理 671003；2.大连理工大学 数学科学学院, 辽宁 大连 116024 )



四叶树Hosoya指标显式公式及其序列

杨 利 民*1， 段 丽 燕1， 王 天 明2

( 1.大理大学 数学与计算机学院, 云南 大理 671003；2.大连理工大学 数学科学学院, 辽宁 大连 116024 )

为研究四叶树Hosoya指标的规律，利用图论的分支分析法，解决了四叶树Hosoya指标的显式公式和序列．对于一般的t叶树，仍然用同样分支分析法，得到相应的t叶树Hosoya指标的显式公式和序列．发现了一族初值不一样的Fibonacci序列，在科学上对组合数学和图论提供了一定参考．

四叶树；t叶树；S(n)-因子；Fibonacci数；Hosoya指标

0 引 言

四叶草又名幸运草，是三叶草或苜蓿草的稀有变种．苜蓿草，是多年生草本植物，一般只有三片小叶子，叶形呈心形，叶心较深色的部分亦是心形．最为有趣也最特别的是，在十万株苜蓿草中，可能只会发现一株是四叶草，因为概率是十万分之一，四叶草成为国际公认的幸运的象征．

由四叶草引出四叶树，四片叶子、顶点数为n的树叫做四叶树．

Fibonacci数列，也称为“兔子数列”，其数列为0，1，1，2，3，5，8，13，21，34，55，89，144，…，满足递归关系式Fn=Fn-1+Fn-2，初值F0=0，F1=1[1-3]．

本文研究四叶树Hosoya指标的显式公式和序列．

1 定义和引理

1.1 定 义

定义1[4]设S(n)={Ki：1≤i≤n}(n≥1)，Ki是i个顶点的完全图．假设M是G的子图并且M的每一个分支都同构于S(n)={Ki：1≤i≤n}(n≥1)中的某一个元素，则称M为图G的一个S(n)={Ki：1≤i≤n}-子图．假设M是图G的生成子图，则称M为图G的一个S(n)={Ki：1≤i≤n}-因子．

令A(G)是图G的所有S(n)={Ki：1≤i≤n}-因子个数．图G是简单图，不包括多重边和环．

定义2 图G的所有k-匹配个数称作Hosoya指标．Hosoya指标用Z(G)表示．

1.2 基本……