图的一种含3-圈和4-圈的2-因子分解  

2-factorization of a Simple Graph Containing Triangle and Quadrilateral

作　　者：卢建立[1] 蔡文娟[1] 

机构地区：[1]河南师范大学数学与信息科学学院,河南新乡453007

出　　处：《河北师范大学学报（自然科学版）》2011年第2期113-118,129,共7页Journal of Hebei Normal University：Natural Science

基　　金：河南省杰出青年计划(084100510013);河南省高校科技创新人才支持计划(2008HASTIT023)

摘　　要：图的独立圈和2-因子问题是因子理论中非常重要的一部分,也是哈密顿圈理论的推广与延伸,其结果主要应用在计算机科学、通信网络设计等方面.利用树形图的思想提出并证明了一个简单图G能被划分成k+1个相互独立的圈,其中恰好含s个3-圈和k-s个4-圈的一个充分条件是:G的顶点个数n≥3s+4(k-s)+4,并且对于G中任意2个不相邻的顶点x和y都满足其度之和d(x)+d(y)≥n+2k-s,这里s,k是2个正整数,并且s<k.The theory of vertex-disjoint cycles and 2-factors of graphs is the extension of the Hamiltonian cycles theory and it has important applications in computer science and network communication. By using arborescence,it is proved that a simple graph G can be divided into k ＋ 1 vertex-disjoint cycles,where s cycles are trian- gles and k - s cycles are quadrilaterals, that is, the number of vertices in G is n ≥3s ＋ 4（k - s） ＋ 4 and d（x） ＋ d（y）≥n ＋2k - s for each pair of nonadjacent vertices x and y in G,where s and k are two positive integers and s 〈 k.

关 键 词：简单图 3-圈 4-圈 划分 2-因子 

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