二分图中哈密顿[k,k+1]因子  

Hamiltonian -factor in bipartite graph

作　　者：王一女[1] 李金娜[1] 

机构地区：[1]沈阳化工学院数理系,辽宁沈阳110141

出　　处：《沈阳航空工业学院学报》2008年第5期88-90,共3页Journal of Shenyang Institute of Aeronautical Engineering

摘　　要：主要研究了在均衡二分图G中哈密顿[k,k+1]因子的存在性。设G=(X,Y,E),|X|=|Y|=n2 4(k-2)-3,k 2且n 2,δ(G)k,若G中每一对不相邻的顶点u,v有m ax{dG(x),dG(x)}n4+2,则G有包含哈密顿圈C的[k,k+1]因子。在此基础上,进一步给出结论:二分图G=(X、Y、E),|X|=|Y|=n2≥4(k-2)且n≥2,δ(G)≥k,若G中每一对不相邻的顶点u,v有dG(v)≥n2+4,则G有包含哈密顿圈C的[k,k+1]因子。结论在很大程度上改进了已有的包含哈密顿圈的度条件,进一步完善了包含哈密顿圈的因子理论。In this paper, we mainly study the existence of Hamiltonian [ k, k ＋ 1 ] - factor. Let be a balanced bipartite graph of order with k ≥ 2, minimum degree at least and ｜X｜=｜Y｜=n/2≥4（k-2）-3,k≥2 for each pair of nonadjacent vertices u and v of G, max{dG（x）,dG（x）}≥n/4＋2, then for any given Hamihonian cycle C, G has a [ k, k ＋ 1 ] - factor containing G. Based on this, we present another conclusion that Let k≥2 be an integer and G be a balanced bipartite graph of order n with minimum degree at least k and ｜X｜=｜Y｜=n/2≥4（k-2）-3, n ≥6. If each pair of nonadjacent vertices u and v of G, dG（u）＋dG（v）≥n/2＋4, then for any given Hamihonian cycle C, G has a [ k, k ＋ 1 ] - factor containing C. This conclusion has improved degree conditions in Hamihonian cycle which have been drawn at some context, and has further perfected fact theory with Hamihonian cycle.

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

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