一类图的第二小和第三小Hosoya指标 A Kind of Graphs with the Second and Third Minimal Hosoya Index

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Advances in Applied Mathematics 应用数学进展 , 2014, 3, 41-47

http://dx.doi.org/10.12677/aam.2014.31007 Published Online February 2014 (//www.abtbus.com/journal/aam.html)

A Kind of Graphs with the Second and Third Minimal

Hosoya Index

Cuo Zhuoma

Department of Mathematics, Qinghai Normal University, Xining

Email: 2353498508@qq.com

Received: Dec. 19th, 2013; revised: Jan. 10th, 2014; accepted: Jan. 22nd, 2014

mits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accordance of the

Creative Commons Attribution License all Copyrights © 201 4 are reserved for Hans and the owner of the intellectual property Cuo

Abstract : The Hosoya index of a graph is defined as the total number of matchings of the graph. Vertex

gluing graph is defined as the cycle in graph only one common vertex. In this paper, we characterize the

graphs with the second and third minimal Hosoya Index, respectively, among the connected graphs with

m -matchings and the gi ven cycl omatic number.

Keywords: Hosoya Index; m-Matching; Vert e x Gl uing Gra ph

一类图的第二小和第三小 Hosoya 指标

卓玛措

青海师范大学数学系，西宁

Email: 2353498508@qq.com

收稿日期： 2013 年 12 月 19 日；修回日期： 2014 年1月10 日；录用日期： 2014 年1月22 日

摘要：图的 Hosoya 指标是指这个图的所有匹配的个数。点粘接图是指图中所含的圈只有一个公共顶

点的图。本文在包含 m-匹配的点粘接双圈图中刻画了具有第二小和第三小 Hosoya 指标的此类图，并

以此为基础在所有包含 m-匹配的点粘接图中刻画了具有第二小和第三小 Hosoya 指标的此类图。

关键词： Hosoya 指标；m-匹配；点粘接图

1. 引言

Hosoya 指标最早由日本化学家 Harruo Hosoya 在文献[1]中引入了以结构描述符号为基础的分子图，他将其

命名为拓扑指标，记作：

。并且他发现该指标与碳氢化合物的物理化学性质，尤其是与它的沸点联系紧密。

这个指标后来被命名为 Hosoya 指标。自此以后，有很多作者研究了 Hosoya 指标[2-7]。

本文所考虑的图都是有限的、无向的简单图。设图

是一个化学分子结构图模型，即为一个具有

个顶点

的连通图，则图

的 Hosoya 指标

( )

，是指一个图的所有匹配情况的数目之和，其中包括空集。所谓

中的

两边独立是指这两条边在

中不相邻。图

的一个

- 匹配是指

个相互独立的边组成的集合。

( )

, Z Gk

表示图

的

- 匹配数。于是，Hosoya 指标是如下定义的：

( )()

ZG ZGk

≥

= ∑

，即

( )

表示一个图中所有匹配情况的

数目之和，规定：对任意图

( )

,0 1 ZG =

，

( )

,1 ZG

等于图

的边数。令

( )

表示

个顶点的一类图，若我们将

( )

OPEN ACCESS 41

卓玛措 | 一类图的第二小和第三小 Hosoya 指标

中所有图的 Hosoya 指标

, ,,

ZZ Z ⋅⋅⋅

按递增的顺序排列为： 123 m

ZZZ Z << <⋅⋅⋅<

，则称

所对应的图是此类图

中 Hosoya 指标最小的图。同理，我们称

所对应的图是此类图中 Hosoya 指标第二小或次小的图。依此类推，

可定义此类图中 Hosoya 指标第三小、第四小、…、第

小的图。

Hou 在文献 [8]中对于包含

- 匹配的树刻画了具有最小和第二小 Hosoya 指标的图。Yu 和Tian 在文献[9]中

对于包含

- 匹配的单圈图刻画了具有最小和第二小 Hosoya 指标的图。Ye 在文献[10]中对于包含

- 匹配的单圈

图刻画了具有第三小至第六小 Hosoya 指标的图。并且在文献[9]中作者对于包含

- 匹配的点粘接双圈图刻画了

具有最小 Hosoya 指标的图。本文在包含

- 匹配的点粘接双圈图中刻画了具有第二小和第三小 Hosoya 指标的此

类图，并以此为基础在所有包含

- 匹配的点粘接图中刻画了具有第二小和第三小 Hosoya 指标的此类图。本文

提到的点粘接图是指图中所含的圈只有一个公共顶点的图。

2. 预备知识

设

是图

的一个匹配 . 如果点

和

中的一条边相连，就称

饱和点

，记作：

vM ∈

，否则称

不饱

和点

，记作

vM ∉

。如果

饱和了图

的所有点，则称

是完美匹配 .如果图

中再也找不到一个匹配

M ′

，

且

′ >

，则称

是最大匹配。显然，完美匹配是最大匹配。我们用

( )

′

表示

中最大匹配所含边数。

设

( )

G ntm

表示阶数为

，

( )

′ =

并且含有

个三角形的点粘接图集。设

( )

U nm

表示阶数为

且

( )

′ =

的所有单圈图集。设

( )

, Bnm

表示阶数为

且

( )

′ =

的所有点粘接双圈图集。设图

( )

1 ,,G ntm

是有

一个公共顶点的

个三角形构成的图，并且在此公共顶点上粘上

mt −−

条长度为 2的路和

21 nm−+

条悬挂边

( 如图 1)。简而言之，我们可以分别用

( )

,1, Gn m

和

( )

,2, Gn m

表示

( )

1 ,

U nm

和

( )

1 ,

B nm

( 如图 1)。设图

( )

,, G ntm

n −2m+ 1

m − t −1

m − t −2

m − t −3

m −2

(n , m)

(8,4)

(n , m)

(10,5)

(n,t,m)

m −3

m −4

m −5

Figure 1. Some unicyclic graphs and bicyclic graphs with m-matching

图 1. 一些具有m-匹配的单圈图和双圈图

OPEN ACCESS

卓玛措 | 一类图的第二小和第三小 Hosoya 指标

也是有一个公共顶点的

个三角形构成的图，并且在此公共顶点上粘上

2 mt−−

条长度为 2的路和

21 nm−+

条

悬挂边，最后将从

( )

,, G ntm

中取出的一条长度为 2 的路作为悬挂点粘在任意一个三角形的另外两个端点上(如

图 1) 。简而言之，我们可以分别用

( )

,1, Gnm

和

( )

,2,

Gn m

表示

( )

2 ,

U nm

和

( )

B nm

( 如图 1)。设

( )

,, G ntm

是有

一个公共顶点的

个三角形构成的图，并且在此公共顶点上粘上

3 mt−−

条长度为 2 的路和

21 nm−+

条悬挂边，

最后将从

( )

,, G ntm

中取出的长度为 2的路粘在此处取出的长度为 2 的路的 2度点上(如图1)。同理，我们可以

分别用

( )

,1,

Gnm

和

( )

,2, Gn m

表示

( )

3 ,U nm

和

( )

3 ,

B nm

( 如图 1)。

若

( )

W VG ⊆

，则用

GW −

表示

的子图，这个子图是通过删去

中的所有点以及与这些点相关连的边而

得到的。类似地，若

( )

E EG

′ ⊆

，则

′

−

是

的子图，这个子图是通过删去

E ′

中的所有边以后得到的。若

{ }

且

{ }

E xy

′ =

，则记作：

Gv −

和

G xy −

。用

( )

表示图

中点

和点

的邻点组成的集合。

引理 1.[7] 设

是一个图且

( )

v VG

∈

，设

,,,

vv v ⋅⋅⋅

是

的邻点，则有：

( )()

{ }

( )

ZGZG vZGvv

= −+−

∑

引理 2.[7] 设

是一个图且

是图

的一条边，则有：

( )(){}

( )

, ZGZG uvZGuv=−+ −

由引理 2 可得：

推论 1. 设

是一个图。若

( )

u VG

∈

是

的一个悬挂点且

是

的唯一的邻点，则有：

( )(){}

( )

, ZGZG uZGuv=−+ −

引理 3.[7] 设图

是由

, ,,

GG G ⋅⋅⋅

个分支构成的，则有：

( )

ZGZG

∏

引理 4.[7] 设

和

分别是

个点的路和星，则对于所有

个点的树

有：

( )

1 n nn

n ZSZTZPF

=≤≤ =

其中

是第

个 Fibonacci 数且：

0 0F=

，

1 F=

。

引理 5.[10] 设

是一个图，并且

是图

的子图，则有：

( )()

ZG ZG ≥

，并且更进一步有：若

()()

EG EG <

，

则有：

()( )

ZG ZG <

。

引理 6.[10] 设

是一个图且

( )()

1 G kk

′ = ≥

，并且

( )

0 G lKkKl≠≥

，则有：

( )

−

≥⋅

等号成立当且仅当

( )()

4 21

2 ,0 G PkKlKl

′′

≅− ≥ 

。

引理 7.[9] 设

() ( )

,2,4 GU nmnmm∈ ≥≥

，则有：

( )()

223 4

ZGn m

−

≥ −+

等号成立当且仅当

( )

, GU nm≅

( 如图 1)。

引理 8.[9] 设

() ()

,2, 4 GUnmnmm

∈ ≥≥

，

( )

, G U nm∉

，则有：

( )()

210 1513

ZGn m

−

≥ −+

等号成立当且仅当

( )

, G U nm≅

( 如图 1) 。

引理 9.[10] 设

( )( )( )

{ }

( )

,\, ,,2,4 GU nmUnmUnmnmm∈ ≥≥

，则有：

( )()

210 1514

ZGn m

−

≥ −+

OPEN ACCESS 43

卓玛措 | 一类图的第二小和第三小 Hosoya 指标

等号成立当且仅当

()( )()

{ }

3 45

,,8,4 ,10,5 GUnmUU∈

( 如图 1) 。

引理 10.[9] 设

() ()

,2, 4

G Bnmnmm ∈ ≥≥

，则有：

( )()

223 5

ZGn m

−

≥ −+

等号成立当且仅当

( )

, GB nm≅

( 如图 1)。

引理 11.[9] 设

( )

,, GG ntm∈

，其中

2 nm≥

，并且

01 tm≤≤ −

。则有：

( )()

2 233

ZGnm t

−

≥− ++

等号成立当且仅当

( )

,, GGntm≅

( 如图 1)。

3. 主要结果和证明

3.1.

( )

, B nm

中具有第二小和第三小 Hosoya指标的图

定理 1. 设图

( )

G Bnm

∈

，

() ()

1 ,2,4GB nmnmm∉ ≥≥

，则有：

( )()

210 1518

ZGn m

−

≥ −+

等号成立当且仅当

( )

GB nm

≅

。

证明：设图

() ()

,2, 4 G Bnmnmm∈ ≥≥

，并且

是图

的一个

- 匹配。我们总可以从图

的圈中找出一

条边

，使得

uv M ∉

，则

G uv −

是一个

个点的连通单圈图。此外，

( )

G uvm

′ −=

( 因为

G uv −

是

的一个

子图，由引理 5，我们有

() ( )

G uvGm

αα

′′

−≤ =

，注意到

是

G uv −

的一个

- 匹配，我们有：

( )

G uvm

′ −≥

，

因此，

( )

G uvm

′ −=

) 。因此

( )

, GuvUn m−∈

，下面我们将分以下三种情形讨论：

( )

, GuvUn m

−≅

，且

( )

, GB nm

≅

，则

( )

{ }

2 1234

, ,,,,

GBnmG GGG ∈

(

1234

,,,

GGGG

见图 2) 。

n −2m+ 1

m −4

n −2m

m −3

Figure 2. Some bicyclic graphs with m-matching

图 2. 一些具有m-匹配的双圈图

由引理 1 直接计算可得：

( )

,210 1518

Z Bnmnm

−

= −+

OPEN ACCESS

卓玛措 | 一类图的第二小和第三小 Hosoya 指标

( )()

210 1522

ZGn m

−

= −+

( )()

2 210 1520

ZGn m

−

= −+

( )

212 1818

ZGnm

−

= −+

( )()

4 212 1822

ZGn m

−

= −+

由此，由上可知：

( )

,, 1,2,3,4

Z GZBnmi >=

。

( )

, GuvUn m−≠

，且

( )

, GB nm≠

。由引理 8得：

( )()

210 1513

Z Guvnm

−

−≥−+

等号成立当且仅当

( )

, GuvUn m−≅

。

注意到：

{ }

, Guv−

是

( )

m −

- 匹配，则有：

{ }

( )

Z Guv

−

−≥

等号成立当且仅当

{}()()

, 222 G uvnmKmK−≅−+−

。容易看出：

必有一点是

( )

, Unm

中的一个

( )

nm −

度点，另一个是

( )

, Unm

中的一个 3 度点，这种情形是不可能出现的。由引理 6得：

{ }

( )

, 52

Z Guv

−

− ≥⋅

等号成立当且仅当

{}()()

24 1

, 422 G uvmKPnmK− ≅−−+

。

由引理 2 得：

( ) (){ }

( )

21015135 2

2101518

ZGZG uvZGuv

Z Bnm

−−

−

= −+ −

≥−+ +⋅

= −+

等号成立当且仅当

( )

, GuvUn m−≅

，且

{}()()

24 1

, 222 G uvmKPnmK− ≅−−+

。容易看出

中的一个

端点是

( )

, Unm

中的一个

( )

−

度点，另一个端点是

( )

, Unm

中一个邻接于 2度点的悬挂点，因此等号成立当

且仅当

( )

, GBnm≅

。

() () ()()

{ }

1 245

,,,,8,4, 10,5 GuvUnmUnm UU−∉

。由引理 9 得：

( )()

210 1514

Z Guvnm

−

−≥−+

等号成立当且仅当

( )

, GuvUn m−≅

。

注意到：

{ }

, G uv

−

是

( )

2 m−

- 匹配，则有：

{ }

( )

Z Guv

−

−≥

等号成立当且仅当

{}( ) ()

, 222 G uvnmKmK−≅−+−



。

从而有：

( )(){}

( )

2101514 2

2101518

ZGZG uvZGuv

Z Bnm

−−

−

= −+ −

≥−++

= −+

等号成立当且仅当

( )

, GuvUn m−≅

，且

{}()()

, 222 G uvmKnmK−≅−−+

，此时

的一个端点必是

( )

, U nm

的一个

( )

nm −

度点，另一个是邻接于一个 3度点的 2度点，从而此时：

( )()

( )

2 ,Z GZBnm≥

。综上所

述，定理得证。

类似定理 1的证明，并且根据引理 5、引理 6、引理 8、引理5和定理 1可得下面的结果：

定理 2.

( )

, G Bnm∈

，

( )( )

{ }

( )

, ,,2,4 GB nmBnmnmm∉ ≥≥

，则：

( )()

210 1519

ZGn m

−

≥ −+

OPEN ACCESS 45

卓玛措 | 一类图的第二小和第三小 Hosoya 指标

等号成立当且仅当

( )

, GBnm≅

。

3.2 .

( )

,, G ntm

中具有第二小和第三小 Hosoya指标的图

对于图

( )

,, Gntm

，我们根据引理 8和定理 1可以得到下面的一般结果：

定理 3. 设

是

( )

,, Gntm

中的一个图，并且

( )

,, GG ntm∉

，其中

2 nm≥

，并且

11 tm≤≤ −

。则：

( )()

2101558

ZGnm t

−

≥− ++

等号成立当且仅当

( )

,, GGntm≅

( 如图 1)。

证明：根据引理 8可知结论对所有的

21 tm≤≤ −

均成立。我们将对

进行归纳来证明以上结论。

当

2 t=

时，根据定理 1 可知结论成立，现在我们假设当

( )

3 t kk

= ≥

时结论成立。

设图

是

() ()

,1,2, 32 G nkmnmkm+≥≤≤ −

中的一个图并且

是图

的一个

- 匹配。我们总可以在

的

一个圈中找到一条边

使得

uv M ∉

。很容易得

() ()

, ,2,32 GuvGn kmnmkm−∈≥≤≤ −

。 (因为

G uv −

是

的一

个子图，所以有

()( )

G uvGm

αα

′′

−≤ =

。注意到

是

G uv −

的一个

- 匹配，则有

( )

G uvm

′ −≥

。因此

( )

G uvm

′ −=

。 )

根据归纳假设可得：

( ) ( )

210 1558

Z Guvnmk

−

− ≥−++

①

等号成立当且仅当

( )

,, GuvGn km−≅

。注意到

{ }

, Guv−

有一个

( )

2 m−

- 匹配，则有：

{ }

( )

Z Guv

−

−≥

。

等号成立当且仅当

{ } ()( )

2 12

, 222 GuvGnmKUmK

−≅−+− 

，容易看出

中必有一个点是

( )

,, Gnkm

中的

一个

( )

1 nmk− +−

度点，另一个端点是

( )

,, Gnkm

中的一个 3 度点，这种情形是不可能的。由引理 6得：

{ }

( )

, 52

Z Guv

−

− ≥⋅

②

等号成立当且仅当

{} ( )()

241

, 422 G uvmKPnmK

− ≅−−+ 

。由引理 2 和不等号①和②得：

( )(){}

( )

,21015585 2

210 155 13

, 1,

ZGZGuvZGuvnmk

n mk

G nkm

−−

−

=−+−≥−++ +⋅

=− ++

= +

③

③的等号成立当且仅当①和②中的等号同时成立。①中的等号成立当且仅当

( )

,, GuvGnkm

−≅

。② 中的等

号成立当且仅当

{}()()

24 1

, 422 G uvmKPnmK− ≅−−+

。

注意到：若

( )

, 1, GG nkm∈+

，

( )

,, GuvGn km−≅

，

{}()()

24 1

, 422 G uvmKPnmK− ≅−−+

。根据

32 km

≤≤ −

，容易看出

中必有一个端点是

( )

,, Gnkm

中的一个

( )

1 nmk− +−

度点，另一个端点是

( )

,, Gnkm

的一个与 2度点相邻接的悬挂点。于是③的等号成立当且仅当

( )

, 1, GG nkm≅+

。定理得证。

类似定理 3的证明，并且根据引理 9和定理 2可得下面的结果：

定理 4. 设

是

( )

,, Gntm

中的一个图，并且

()()

{ }

,, ,,, GGntm Gntm∉

，其中

nm ≥

，并且

tm ≤≤ −

。则：

( )()

2101559

ZGnm t

−

≥− ++

等号成立当且仅当

( )

,, GG ntm

≅

。

参考文献 (References)

[1] Hosoya, H. (1971) Topological index, a newly propo sed quantity character izing th e topo logical natu re of structu ral iso mers of satu rated h ydro-

OPEN ACCESS

卓玛措 | 一类图的第二小和第三小 Hosoya 指标

carbons . Bulletin of the Chemical Society of Japan, 44 , 2332 -2339.

[2] Cyvin, S.J. and Gutman, I. (1989) Hosoya index of fused molecules. MATCH: Communications in Math ematical and in Computer Chemistry,

23 , 89-94.

[3] Cyvin, S.J., Gutman, I. and Kolakovic, N. (1989) Hosoya index of some polymers. MATCH: Communications in Mathematical and in Com-

puter Chemistry , 24, 105-117.

[4] Gutman, I. (1988) On the Hosoya index of very large molecules . MATCH: Communications in Mathematical a nd in Computer Chemistry, 23,

95 - 103.

[5] Turker, L. (2003) Contemplation on the Hosoya indices. Journal of Molecular St r ucture: Theochem, 623, 57-77.

[6] Bondy, J.A. and Murty, U.S.R. (1976) Graph theory with applications. North-Holland, Amsterdam.

[7] Zhang, L.Z. and Tian, F. (2003) Extremal catacondensed benzenods. Journal of Mathematical Chemistry, 34, 111-122.

[8] Hou, Y.P. (2002) On acyclic systems with minimal Hosoya index. Discrete Applied Mathematics, 119, 251-257.

[9] Yu, A.M. and Tian, F. (2006) A Kind of graphs with minimal Hosoya i ndices and maximal Merrifield-Si mmons indices. MATCH: Communi-

cations in Mathematical and in Computer Chemistry , 55, 103-118.

[10] Ye, C.F. (2012 ) Unicyclic graphs with the third smallest to sixth smallest Hosoya Index. MATCH: Communications in Mathematical and in

Computer Chemistry , 55, 593-604.

OPEN ACCESS 47