二分图中存在哈密顿[k,k+1]因子的条件  

Condition on Hamiltonian Factor in Bipartite Graph

作　　者：李金娜[1] 张庆灵[2] 谢彦红[1] 

机构地区：[1]沈阳化工学院数理系,辽宁沈阳110142 [2]东北大学系统科学研究所,辽宁沈阳110004

出　　处：《沈阳化工学院学报》2007年第4期314-316,共3页Journal of Shenyang Institute of Chemical Technolgy

基　　金：国家自然科学基金资助项目(60574011)

摘　　要：主要研究在均衡二分图G中哈密顿[k,k+1]因子的存在性.根据图论中因子和度的理论,针对均衡二分图,研究图G的阶、最小度、顶点之间距离三者之间的关系.通过对每一对距离为2的顶点度的限制,分情况讨论并给出图G存在包含哈密顿圈C的[k,k+1]因子的充分条件.如果G的每一对距离为2的顶点u,v有max{dG(u),dG(v)}n4+2,则对G的任意哈密顿圈C,G有[k,k+1]因子包含圈C.在很大程度上改进了已有的包含哈密顿圈C的度的条件,进一步完善了包含哈密顿圈C的因子理论.算例表明此结论的有效性.Existence of Hamiltonian [ k, k ＋ 1 ] factor is studied. Based on factor and degree of graph theory and aiming to balance bipartite graph, a sufficient condition on the existence of Hamiltonian [ k, k ＋ 1 ] factor in balanced bipartite graph is presented by straining the maximum degree of each pair of vertices whose distance is 2. If for each pair of nonadjacent vertices u and v of G, max{ dG（x） ,de（x）}≥ n/4 ＋ 2, then for any given Hamiltonian cycle C, G has a [ k, k ＋ 1 ] factor containing C. This greatly 4 improves the old degree conditions on having Hamiltonian cycle, and further perfects factor theory with Hamiltonian cycle. An example illustrates the validity of the proposed approach.

关 键 词：均衡二分图 [k k+1]因子 哈密顿圈 

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