应用数学进展    Vol.3 No.1 (February 2014)

无爪图中子图的度和与Hamilton连通性
The Hamilton-Connectivity with the Sum Degree of Subgraph in Claw-Free Graphs

作者: 米 晶 , 王江鲁 ：山东师范大学数学科学学院，济南;

关键词: 无爪图； 不相邻子图； 子图的度； Hamilton路； Claw-Free Graph； Non-Adjacent Subgraph； Degree of Subgraph； Hamilton-Path

摘要:
本文定义了子图的度的概念，并利用子图的度给出如下结果：设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 H1 and H2, any two non-adjacent subgraphs, are isomorphic to P3 and K2, respectively, and d(H1) + d(H2) ≥ n, for each pair of u,v Î G, when {u,v} isn’t a cut set, there exists a Hamilton-path in u,v.

文章引用: 米 晶 , 王江鲁 (2014) 无爪图中子图的度和与Hamilton连通性。 应用数学进展， 3， 8-16. doi: 10.12677/AAM.2014.31002

参考文献

[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.

分享
Top