关于单圈图的Hosoya指标研究

作者：艺术职称论文发表     人气：539     来源：     标签：

用 表示图 的 指标，G是有n个顶点的图,定义为图 的边的匹配数的总和。设 表示 个顶点的单圈图集。一个充分悬挂的单圈图具有这样的性质：在它唯一圈上的任意一点的度不小于3。用 表示充分悬挂的单圈图集。在这篇文章中，确定了在 中有第七小 指标的图。有最小Hosoya指标的树.Ou在[5]中唯一确定了n个点的单圈图中有第一大和第二大Hosoya指标的单圈图,他在[5]中也分别确定了有第一小,第二小Hosoya指标的单圈图.而且Hua在[6]中确定了n个点的充分悬挂的单圈图中。

设 是具有 个顶点的图，Hosoya指标被定义为图 的所有匹配数的总和，用 表示，即 ，其中 表示 中 -匹配的个数。设 是有 个顶点的图,它的邻接矩阵是A(G)。 的邻点式矩阵B(G),定义为B(G)= A(G)+I,其中I是 阶单位矩阵。一个 -匹配是有 条边的边集 的子集，其中 且 中任何两条边都不相邻，为了简便和一致通常规定 .确定有极值Hosoya指标的图有着重要的意义，近年来已提出了很多结果。 在文献[1]中证明了所有六边形链中，直六边形链中有最小的Hosoya指标。 在文献[2]中证明了所有正六边形链中， 字形链有最大的Hosoya指标。设 表示了有 个顶点的单圈图集，一个充分悬挂的单圈图是这样一个单圈图：在它的唯一图中的任何一点的度不小于3。本文中主要研究充分悬挂单圈图的Hosoya指标，确定了在 中有第七小Hosoya指标的充分悬挂单圈图。

引理1^[1]设 的 个分支为 , ,…, ,则 = .

引理2^[1] 设 是 ( ≥2)个顶点的图，若 是 的悬挂边， 是悬挂点，则 = .

引理3 ^[1]设 是 个顶点的单圈图， ( 3)则 .其中 是 去掉圈 得到的森林且 .

下面介绍两种能够减少图 的匹配数的变换即减少图 的Hosoya指标。

 

 

 

 

 

 

 

引理4 ^[2] 设 和 是图1中所示的图，则 ＞ .

 

 

                                                 3

  

                                       

        

引理5 ^[2] 设 1， 2和 3如图2中所示，则 ( 1) ＞ ( 2)或 ( 1) ＞ ( 3)

引理6 ^[2]  设 是一个图，且 ,若 是 的邻点，则 .若图 的分支是 ，则

引理7^[3] 设 ≥8, ,则 ≥5n-6 当且仅当 取等号。

引理8 ^[3]  设 ≥8,则 在 中取得第二小Hosoya指标。

引理9 ^[4]  设 ≥10在 中，若10≤ ≤12, 取得第三小Hosoya指标，而当 ≥13, 取得第三小Hosoya指标，其 如图3。

                 

 

 

 

 

 

图3  

 

第三小Hosoya指标的单圈图

引理10 ^[4]  设 ≥12,在 中，若12≤ ≤14, 取得第四小Hosoya指标，而当 ≥14， 取得第四小Hosoya指标，其 如图4：

 

                                   

 

 

 

                    

图4  第四小Hosoya指标的单圈图

引理11 ^[5] ：设 ,则 在 中取得第五小 指标。

引理12 ^[5] ：设 ,则 在 中取得第六小 指标，其中 如下图2.5所示：

 

 

                                                   

图5

定理1：设 ，且

,则 当且仅当 时等号成立，其中 ， ， ， 如图6所示：

                                               

 

图6

证明：分两种情形讨论.

情形1：若 .

由于 , , , ,所以( , , )≠(1,1， -5), (1,2， -6), (1,3， -7),（2，2， -7）。假设( , , )≠(1,4， -8)且 ≤ ≤ ，分以下两种情形：

情形1.1：k1=1

由于 ≠1，2，3，所以 ≥5，把 看作 0，对 施行 变换，由引理5得： ＞ = 或者 ＞ = 。由引理1，2，3得： =  -2＞ -2= =

情形1.2： ≥2.

对 施行 变换，由引理5得： ＞ .若 定理成立。否则有 再施行一次 变换有，

＞

= 或者

＞ = .由引理1，2，3得： ＞ = .

情形2：若 分以下八种情形讨论：

情形2.1：若对 连续施行 变换得 .

由于 ，则由引理4，对 至少施行一次 变换，先考虑对 刚好施行一次 变换化为 .由于 .则 为 且 .如图7所示：

图7

 

由引理8计算得： = ， = .因此 - = .

设 = .则 = .因此得：当 ，有 ＞0，故当 时， - = = ＞0 .

当 时， ＜0，故 - = ＞0从而 ＞ .

情形2.2：若对 连续施行 变换得 .

由于 ，则有引理4，对 至少施行一次 变换，先考虑对 刚好通过一次 变换化为 ，则 为 ， (3),如图8所示：

 

 

图8

由引理8计算得： .因此得： - = .设 =

则 = .当 时，有 ＞0，所以 - = = ＞0；当 时，有 ＜0，则 - = = ＞0 ，所以 ＞ .

情形2.3：若对 连续施行两次 变换得 .

由于 ，则对 至少施行一次 变换，先考虑对 通过一次 变换化为 ，则 或 或 .其中， ， ， (3)如图9所示：

 

 

图9

 

若 ，由引理8计算得： = 因此得： - = 设 = 则 = .当 时， ＞0，有 - = = ＞0( ≥16).当 时，有 ＜0，

则 - = ＞0( ≥16).故 ＞ .

若 ，由引理8计算得： = .显然， = ≥ = .所以 ＞ .

情形2.4：若对 连续施行 变换得 .

由于 ，则由引理4，对 至少施行一次 变换，先考虑对 刚好通过一次 变换化为 ，则 ， (3)，如图10所示：

 

 

图10

若 ，由引理8计算得： = .因此得： - = .当 时， ＜0. - = ＞0( ≥16).故 ＞ .

情形2.5：若对 连续施行 变换得 .

由于 ，则由引理4，对 至少施行一次 变换得 ，先考虑对 刚好通过一次 变换得 ，则 ， (3)，如图11所示：

 

图11

若 ，由引理8计算得： = .因此得： - = .设 = ，则 = 当 时， ＞0， - = = ＞0( ≥16)；当 时， ＜0， - = ＞0( ≥16).所以， ＞ .

若 至少通过两次 变换，使 化为 ，则 类似于图12所示：

 

 

图12

对 通过一系列的 变换，使 化为 ，则由引理4知， ＞ ,而 ＞ ，所以， ＞ .

情形2.6：若对 连续施行 变换得 .

由于 ，则由引理4，对 至少施行一次 变换得 ，先考虑对 刚好通过一次 变换化为 ，则 或 .其中， ， (3)如图13所示：

图13

若 ，由引理8计算得： = .因此得： - = .设 = ，则 = .当 时，，有 - = ＞0( ≥16).则 - = = ＞0( ≥16).故 ＞ .

若 ，由引理8计算得： = ＞ - ＞0.故 ＞ .

若 (3)，至少通过两次 变换化为 ，则 类似于图14所示：

 

图14

对 通过一系列的 变换，使 化为 或 ，则由引理4知， ＞ ， ＞ ，而 ＞ ， ＞ ，所以 ＞ .

情形2.7： 通过连续 变换化为 .

先考虑 刚好通过一次 变换化为 ，则 为 且 或 ，其中 ， (3)，如下图15所示：

                                         

图15

若 ，由引理8计算得： = .设 = - = .则 = ，当 时， ＞0. - = = ＞0；当 时， ＜0，则 - = = ＞0（ ），所以 ＞ .

若 ，情形2.1已证明， ＞ .

 

若 至少施行两次 变换得 ，其方法类似2.1则对 通过一系列 变换化为 或 ，由引理4知： ＞ .

情形2.8：对 通过一系列的 变换不能化成： ， ， ， ， ， ， .对 重复施用 变换可得： 且 ，由引理4知，可得： ＞ ，而由情形1知， ＞ ，所以 ＞ 。

综上所述，当 时， ,

, , }时，有 ，当且仅当 时取等号。

定理2：在 的图簇 中， 取得第七小 指标.

证明：由引理6、7得：当 时， ＞ ，由引理1、2、3得： =12 -62＞11 -70= ,由引理9、10、11、12和定理1得证。

Hosoya指标作为重要的拓扑参数之一，在研究碳氢化合物的分子结构和其物理化学性质的关系中，起了重要的作用，文中得出了关于图的Hosoya指标的重要结果，在n个顶点的单圈图集中，当 的图簇 中， 取得第七小 指标。