均衡二分图中存在哈密顿因子的条件  

Condition on existence of Hamiltonian factor in balanced bipartite graph

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

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

出　　处：《辽宁工程技术大学学报（自然科学版）》2009年第4期676-678,共3页Journal of Liaoning Technical University (Natural Science)

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

摘　　要：研究了在均衡二分图中包含给定哈密顿圈的[k,k+1]因子的存在性问题。根据图论中因子和临界图理论,并结合代数知识,针对均衡二分图,研究图的阶数,顶点的度和因子之间的关系,分情况讨论,通过对均衡二分图的临界条件的限制,给出均衡二分图中存在包含给定的哈密顿圈的[k,k+1]因子的充分条件。该条件在很大程度上改进了已有的包含哈密顿圈的度条件,进一步完善了包含哈密顿圈的因子理论。算例表明所用方法的有效性,所得结论的正确性。An investigation is conducted to study the existence of Hamiltonian[k,k ＋ 1] factor in a balanced bipartite graph. Based on the factors in graph theory and the critical graph, this paper presents the relationship among the graph order, vertex degree and factor. The sufficient conditions for the existence of Hamiltonian [k, k ＋ 1] factor with a given Hamiltonian cycle in a balanced bipartite graph are given by restricting the critical conditions in a balanced bipartite graph. The sufficient conditions greatly improve the existing degree conditions with Hamiltonian cycle, and also improve the factor theory with Hamiltonian cycle. An experimental example shows that the proposed approach is valid.

关 键 词：均衡二分图 [k k+1]因子 (n/4)+1临界图 

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