Hamilton图中的H圈数  

The Number of Hamilton Cycles in a Hamilton Graph

作　　者：王明磊[1] 施永兵[1] 

机构地区：[1]上海师范大学数理信息学院,上海200234

出　　处：《上海师范大学学报（自然科学版）》2004年第1期39-41,共3页Journal of Shanghai Normal University(Natural Sciences)

基　　金：上海市高校科技发展基金(02DK08);上海市教委课程建设项目.

摘　　要：设Γk={G||E(G)|-|V(G)|=k且G是至少有3个顶点的H图},Γn,k={G|G是阶为n≥3的图且|E(G)|-|V(G)|=k}.用f(G)表示图G的H圈数.令h(k)=max{f(G)|G∈Γk}和h(n,k)=max{f(G)|G∈Γn,k}.作者得到h(k)的上界和下界,并且当n为大于等于k的奇数以及k≤n2+1时,确定了h(n,k).The set of Hamilton graphs with |E(G)|-|V(G)|=k and at least three vertices is denoted by Γ_k. The set of Hamilton graphs with |E(G)|-|V(G)|=k and n vertices is denoted by Γ_(n,k) and the number of Hamilton cycles of a graph G is denoted by f(G). Let h(k)= max {f(G)|G∈Γ_k} and h(n,k)= max {f(G)|G∈Γ_(n,k)} . In this paper, we get a lower and upper bound of h(k), and determine h(n,k) when n is an odd with n≥k or k≤n2+1.

关 键 词：圈 HAMILTON圈 最大H圈数 

分 类 号：O157.5[理学—数学]