无爪图中子图的度和与Hamilton连通性
The Hamilton-Connectivity with the Sum Degree of Subgraph in Claw-Free Graphs
摘要:
本文定义了子图的度的概念,并利用子图的度给出如下结果:设
G是n阶2-连通无爪图,δ(G)≥3,如果G中任意两个分别同构于P3和K2的不相邻子图H1,H2的度和,对于任意的u,vÎG,若{u,v}不构成割集,那么u,v间存在Hamilton路。
Abstract:
In this paper
,
we defined the degree of subgraph, and got the following result on the basis of the degree of subgraph: Let
G
be a 2-connected claw-free graph of order
n
,
.
If
H
1
and
H
2
,
any two non
-
adjacent subgraphs
, are
isomorphic to
P
3
and
K
2
,
respectively
,
and
d
(
H
1
) +
d
(
H
2
) ≥
n
,
for each pair of
u
,
v
Î
G
,
when
{
u
,
v
} isn
’
t a cut set,
there
exis
ts
a Hamilton-path in
u
,
v
.
参考文献
[1] |
Bondy, J.A. and Murty, U.S.R. (1976) Graph theory with applications. Macmillan London and Elsevier, New York. |
[2] |
Dirac, G.A. (1952) Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 3, 269-281. |
[3] |
Ore, O. (1960) Note on Hamilton circuits. American Mathematical Monthly, 67, 55. |
[4] |
Matthews, M.M. and Summer, D.P. (1985) Longest paths and cycles in K1,3-free graphs. Graph Theory, 9, 269-277. |
[5] |
Flandrin, E., Fournier, I. and Germa, A. (1988) Circumference and Hamiltonism in K1,3-free graphs. Annals of Discrete Mathematics, 41, 131-140. |