Figure 1. Some unicyclic graphs and bicyclic graphs with m-matching
图1.一些具有m-匹配的单圈图和双圈图
OPEN ACCESS
42
卓玛措|一类图的第二小和第三小 Hosoya 指标
也是有一个公共顶点的
t
个三角形构成的图，并且在此公共顶点上粘上
2mt−−
条长度为 2的路和
21nm−+
条
悬挂边，最后将从
( )
1
,,G ntm
中取出的一条长度为 2的路作为悬挂点粘在任意一个三角形的另外两个端点上(如
图1)。简而言之，我们可以分别用
( )
2
,1,Gnm
和
()
2
,2,
Gn m
表示
()
2,
U nm
和
()
2
,
B nm
(如图 1)。设
( )
3
,,G ntm
是有
一个公共顶点的
t
个三角形构成的图，并且在此公共顶点上粘上
3mt−−
条长度为 2的路和
21nm−+
条悬挂边，
最后将从
( )
2
,,G ntm
中取出的长度为 2的路粘在此处取出的长度为 2的路的 2度点上(如图1)。同理，我们可以
分别用
()
3
,1,
Gnm
和
( )
3
,2,Gn m
表示
( )
3,U nm
和
( )
3,
B nm
(如图 1)。
若
( )
W VG⊆
，则用
GW−
表示
G
的子图，这个子图是通过删去
W
中的所有点以及与这些点相关连的边而
得到的。类似地，若
( )
E EG
′⊆
，则
GE
′
−
是
G
的子图，这个子图是通过删去
E′
中的所有边以后得到的。若
{}
Wv
=
且
{}
E xy
′=
，则记作：
Gv−
和
G xy−
。用
( )
G
Nv
表示图
G
中点
v
和点
v
的邻点组成的集合。
引理 1.[7]设
G
是一个图且
()
v VG
∈
，设
12
,,,
t
vv v⋅⋅⋅
是
v
的邻点，则有：
( )()
{ }
( )
1
,
t
i
i
ZGZG vZGvv
=
= −+−
∑
引理 2.[7]设
G
是一个图且
uv
是图
G
的一条边，则有：
( )(){}
( )
,ZGZG uvZGuv=−+ −
由引理 2可得：
推论 1. 设
G
是一个图。若
()
u VG
∈
是
G
的一个悬挂点且
v
是
u
的唯一的邻点，则有：
( )(){}
( )
,ZGZG uZGuv=−+ −
引理 3.[7]设图
G
是由
12
, ,,
t
GG G⋅⋅⋅
t
个分支构成的，则有：
( )
()
1
t
i
i
ZGZG
=
=
∏
引理 4.[7]设
n
P
和
n
S
分别是
n
个点的路和星，则对于所有
n
个点的树
T
有：
( )
( )
( )
1n nn
n ZSZTZPF
+
=≤≤ =
其中
n
F
是第
n
个Fibonacci 数且：
00F=
，
1
1F=
。
引理 5.[10]设
G
是一个图，并且
1
G
是图
G
的子图，则有：
( )()
1
ZG ZG≥
，并且更进一步有：若
()()
1
EG EG<
，
则有：
()( )
1
ZG ZG<
。
引理 6.[10]设
G
是一个图且
( )()
1G kk
α
′= ≥
，并且
( )
12
0G lKkKl≠≥
，则有：
( )
2
52
k
ZG
−
≥⋅
等号成立当且仅当
( )()
4 21
2 ,0G PkKlKl
′′
≅− ≥
。
引理 7.[9]设
() ( )
,2,4GU nmnmm∈ ≥≥
，则有：
( )()
2
223 4
m
ZGn m
−
≥ −+
等号成立当且仅当
( )
1
,GU nm≅
(如图 1)。
引理 8.[9]设
() ()
,2, 4GUnmnmm
∈ ≥≥
，
( )
1
,G U nm∉
，则有：
( )()
4
210 1513
m
ZGn m
−
≥ −+
等号成立当且仅当
( )
2
,G U nm≅
(如图 1)。
引理 9.[10]设
( )( )( )
{ }
( )
12
,\, ,,2,4GU nmUnmUnmnmm∈ ≥≥
，则有：
( )()
4
210 1514
m
ZGn m
−
≥ −+
OPEN ACCESS43
卓玛措|一类图的第二小和第三小 Hosoya 指标
等号成立当且仅当
()( )()
{ }
3 45
,,8,4 ,10,5GUnmUU∈
(如图 1)。
引理 10.[9]设
() ()
,2, 4
G Bnmnmm∈ ≥≥
，则有：
( )()
2
223 5
m
ZGn m
−
≥ −+
等号成立当且仅当
( )
1
,GB nm≅
(如图 1)。
引理 11.[9]设
( )
,,GG ntm∈
，其中
2nm≥
，并且
01tm≤≤ −
。则有：
( )()
2
2 233
m
ZGnm t
−
≥− ++
等号成立当且仅当
( )
1
,,GGntm≅
(如图 1)。
3. 主要结果和证明
3.1.
( )
,B nm
中具有第二小和第三小Hosoya指标的图
定理 1.设图
( )
,
G Bnm
∈
，
() ()
1,2,4GB nmnmm∉ ≥≥
，则有：
( )()
4
210 1518
m
ZGn m
−
≥ −+
等号成立当且仅当
()
2
,
GB nm
≅
。
证明：设图
() ()
,2, 4G Bnmnmm∈ ≥≥
，并且
M
是图
G
的一个
m
-匹配。我们总可以从图
G
的圈中找出一
条边
uv
，使得
uv M∉
，则
G uv−
是一个
n
个点的连通单圈图。此外，
( )
G uvm
α
′−=
(因为
G uv−
是
G
的一个
子图，由引理 5，我们有
() ()
G uvGm
αα
′′
−≤ =
，注意到
M
是
G uv−
的一个
m
-匹配，我们有：
( )
G uvm
α
′−≥
，
因此，
( )
G uvm
α
′−=
)。因此
( )
,GuvUn m−∈
，下面我们将分以下三种情形讨论：
1)
( )
1
,GuvUn m
−≅
，且
()
1
,GB nm
≅
，则
( )
{ }
2 1234
, ,,,,
GBnmG GGG∈
(
1234
,,,
GGGG
见图 2)。
n−2m+ 1
n−2m+ 1
m−4
m−4
n−2m
n−2m
m−3
m−3
G
1
G
2
G
3
G
4
Figure 2. Some bicyclic graphs with m-matching
图2.一些具有m-匹配的双圈图
由引理 1直接计算可得：
( )
( )
( )
4
2
,210 1518
m
Z Bnmnm
−
= −+
OPEN ACCESS
44
卓玛措|一类图的第二小和第三小 Hosoya 指标
( )()
4
1
210 1522
m
ZGn m
−
= −+
( )()
4
2210 1520
m
ZGn m
−
= −+
( )
( )
4
3
212 1818
m
ZGnm
−
= −+
( )()
4
4212 1822
m
ZGn m
−
= −+
由此，由上可知：
()
( )
( )
()
2
,, 1,2,3,4
i
Z GZBnmi>=
。
2)
( )
1
,GuvUn m−≠
，且
( )
1
,GB nm≠
。由引理 8得：
( )()
4
210 1513
m
Z Guvnm
−
−≥−+
等号成立当且仅当
( )
2
,GuvUn m−≅
。
注意到：
{ }
,Guv−
是
( )
2
m−
-匹配，则有：
{ }
( )
2
,2
m
Z Guv
−
−≥
等号成立当且仅当
{}()()
12
, 222G uvnmKmK−≅−+−
。容易看出：
uv
必有一点是
( )
2
,Unm
中的一个
( )
nm−
度点，另一个是
( )
2
,Unm
中的一个 3度点，这种情形是不可能出现的。由引理 6得：
{ }
( )
4
, 52
m
Z Guv
−
− ≥⋅
等号成立当且仅当
{}()()
24 1
, 422G uvmKPnmK− ≅−−+
。
由引理 2得：
() (){ }
( )
()
( )
()
( )
44
4
2
,
21015135 2
2101518
,
mm
m
ZGZG uvZGuv
nm
nm
Z Bnm
−−
−
= −+ −
≥−+ +⋅
= −+
=
等号成立当且仅当
( )
2
,GuvUn m−≅
，且
{}()()
24 1
, 222G uvmKPnmK− ≅−−+
。容易看出
uv
中的一个
端点是
( )
2
,Unm
中的一个
( )
nm
−
度点，另一个端点是
()
2
,Unm
中一个邻接于 2度点的悬挂点，因此等号成立当
且仅当
( )
2
,GBnm≅
。
3)
() () ()()
{ }
1 245
,,,,8,4, 10,5GuvUnmUnm UU−∉
。由引理 9得：
( )()
4
210 1514
m
Z Guvnm
−
−≥−+
等号成立当且仅当
( )
3
,GuvUn m−≅
。
注意到：
{}
,G uv
−
是
()
2m−
-匹配，则有：
{ }
( )
2
,2
m
Z Guv
−
−≥
等号成立当且仅当
{}() ()
12
, 222G uvnmKmK−≅−+−
。
从而有：
( )(){}
( )
( )
( )
( )
( )
42
4
2
,
2101514 2
2101518
,
mm
m
ZGZG uvZGuv
nm
nm
Z Bnm
−−
−
= −+ −
≥−++
= −+
=
等号成立当且仅当
( )
3
,GuvUn m−≅
，且
{}()()
21
, 222G uvmKnmK−≅−−+
，此时
uv
的一个端点必是
( )
3
,U nm
的一个
( )
nm−
度点，另一个是邻接于一个 3度点的 2度点，从而此时：
( )()
( )
2,Z GZBnm≥
。综上所
述，定理得证。
类似定理 1的证明，并且根据引理 5、引理 6、引理 8、引理5和定理 1可得下面的结果：
定理 2.
( )
,G Bnm∈
，
( )( )
{ }
( )
12
, ,,2,4GB nmBnmnmm∉ ≥≥
，则：
( )()
4
210 1519
m
ZGn m
−
≥ −+
OPEN ACCESS45
卓玛措|一类图的第二小和第三小 Hosoya 指标
等号成立当且仅当
( )
3
,GBnm≅
。
3.2.
( )
,,G ntm
中具有第二小和第三小Hosoya指标的图
对于图
( )
,,Gntm
，我们根据引理 8和定理 1可以得到下面的一般结果：
定理 3.设
G
是
( )
,,Gntm
中的一个图，并且
( )
1
,,GG ntm∉
，其中
2nm≥
，并且
11tm≤≤ −
。则：
( )()
4
2101558
m
ZGnm t
−
≥− ++
等号成立当且仅当
( )
2
,,GGntm≅
(如图 1)。
证明：根据引理 8可知结论对所有的
21tm≤≤ −
均成立。我们将对
t
进行归纳来证明以上结论。
当
2t=
时，根据定理 1可知结论成立，现在我们假设当
( )
3t kk
= ≥
时结论成立。
设图
G
是
() ()
,1,2, 32G nkmnmkm+≥≤≤ −
中的一个图并且
M
是图
G
的一个
m
-匹配。我们总可以在
G
的
一个圈中找到一条边
uv
使得
uv M∉
。很容易得
() ()
, ,2,32GuvGn kmnmkm−∈≥≤≤ −
。(因为
G uv−
是
G
的一
个子图，所以有
()( )
G uvGm
αα
′′
−≤ =
。注意到
M
是
G uv−
的一个
m
-匹配，则有
( )
G uvm
α
′−≥
。因此
( )
G uvm
α
′−=
。)
根据归纳假设可得：
( )( )
4
210 1558
m
Z Guvnmk
−
− ≥−++
①
等号成立当且仅当
( )
2
,,GuvGn km−≅
。注意到
{ }
,Guv−
有一个
( )
2m−
-匹配，则有：
{ }
( )
2
,2
m
Z Guv
−
−≥
。
等号成立当且仅当
{ }()( )
2 12
, 222GuvGnmKUmK
−≅−+−
，容易看出
uv
中必有一个点是
( )
2
,,Gnkm
中的
一个
( )
1nmk− +−
度点，另一个端点是
( )
2
,,Gnkm
中的一个 3度点，这种情形是不可能的。由引理 6得：
{}
()
4
, 52
m
Z Guv
−
− ≥⋅
②
等号成立当且仅当
{}( )()
241
, 422G uvmKPnmK
− ≅−−+
。由引理 2和不等号①和②得：
( )(){}
( )
( )
( )
( )
( )
44
4
2
,21015585 2
210 155 13
, 1,
mm
m
ZGZGuvZGuvnmk
n mk
G nkm
−−
−
=−+−≥−++ +⋅
=− ++
= +
③
③的等号成立当且仅当①和②中的等号同时成立。①中的等号成立当且仅当
( )
2
,,GuvGnkm
−≅
。②中的等
号成立当且仅当
{}()()
24 1
, 422G uvmKPnmK− ≅−−+
。
注意到： 若
( )
, 1,GG nkm∈+
，
( )
2
,,GuvGn km−≅
，
{}()()
24 1
, 422G uvmKPnmK− ≅−−+
。根据
32km
≤≤ −
，容易看出
uv
中必有一个端点是
( )
2
,,Gnkm
中的一个
( )
1nmk− +−
度点，另一个端点是
( )
2
,,Gnkm
的一个与 2度点相邻接的悬挂点。于是③的等号成立当且仅当
( )
2
, 1,GG nkm≅+
。定理得证。
类似定理 3的证明，并且根据引理 9和定理 2可得下面的结果：
定理 4.设
G
是
( )
,,Gntm
中的一个图，并且
()()
{ }
12
,, ,,,GGntm Gntm∉
，其中
2
nm≥
，并且
11
tm≤≤ −
。则：
( )()
4
2101559
m
ZGnm t
−
≥− ++
等号成立当且仅当
( )
3
,,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
46
卓玛措|一类图的第二小和第三小 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
