3-连通无爪图Hamilton连通性的一个定理
首发时间:2007-10-25
摘要:hamilton-连通性问题是图论中重要问题之一。O.Ore已证明了如下的著名定理:对于n阶图G中任意两个不相邻顶点u和v,若满足d(u)+d(v)≥n+1,则G为hamilton-连通的。本文要对无爪图进行讨论,并使用反证法,通过构造最长路并得出矛盾的方法,得到了关于3-连通无爪图Hamilton连通性的一个定理。
关键词: 3-连通 无爪图 hamilton-连通图
For information in English, please click here
A Theorem about the Hamilton-Connectedness of 3-connected Claw-Free Graphs
Abstract:The problem on hamilton-connectedness of graphs is a very important problem in graph theory and the research is very active. A well-known result by O.Ore is that every graph of order n with d(u)+d(v)≥n+1 for any pair of nonadjacent vertices u and v is hamiltonian connected. In this paper we consider claw-free graphs, by the way of constructing the longest path and reduction to absurdity, we get a theorem about the hamilton-connectedness of 3-connected claw-free graphs.
基金:
论文图表:
引用
No.1592714023311933****
同行评议
共计0人参与
勘误表
3-连通无爪图Hamilton连通性的一个定理
评论
全部评论0/1000