k-连通的强-［k+4,2］图的Hamilton路

doi:10.3976/j.issn.1002-4026.2011.06.002

山东科学 ›› 2011, Vol. 24 ›› Issue (6): 5-7.doi: 10.3976/j.issn.1002-4026.2011.06.002

k-连通的强-［k+4,2］图的Hamilton路

刘燕, 王江鲁

山东师范大学数学科学学院，山东济南 250014

收稿日期:2011-05-04 出版日期:2011-12-20 发布日期:2011-12-20
作者简介:刘燕（1987-）,女，硕士研究生，研究方向为图论与组合优化。Email:liuyan2011yan@126.com

Hamilton path of a k-connected strong-［k+4,2］ graph

LIU Yan, WANG Jiang-Lu

School of Mathematics, Shandong Normal University, Jinan 250014, China

Received:2011-05-04 Online:2011-12-20 Published:2011-12-20

摘要/Abstract

摘要：

如果G的任意s个点的导出子图中至少含有t条独立边，则称图G为强-［s,t］图。本文证明了以下结果：设G是k-连通的强-［k+4,2］图，且δ≥k+1,则G或者有Hamilton路或者同构于(∪^k+2_i=1H_i)∨G_k，其中H_i≌K₂,i=1,2…k+2,G_k是含有k个点的任意图。

关键词: 强［s,t］-图, Hamilton路, k-连通图

Abstract:

A graph G is a strong -［s,t］ graph if there are at least t independent edges in every included subgraph of s vertices. This paper proves that if G is a k-connected strong -［k+4,2］ graph with δ≥k+1, then G has a Hamilton path or is isomorphic to (∪^k+2_i=1H_i)∨G_k,where H_i≌K₂,i=1,2…k+2，and G_k is an arbitrary graph of k vertices.

Key words: strong -［s,t］ graph, Hamilton path, k-connected graphs

中图分类号:

O157.5

刘燕, 王江鲁. k-连通的强-［k+4,2］图的Hamilton路[J]. 山东科学, 2011, 24(6): 5-7.

LIU Yan, WANG Jiang-Lu. Hamilton path of a k-connected strong-［k+4,2］ graph[J]. Shandong Science, 2011, 24(6): 5-7.

k-连通的强-［k+4,2］图的Hamilton路

Hamilton path of a k-connected strong-［k+4,2］ graph

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 0