期刊信息
- 刊名： 河北师范大学学报（自然科学版）Journal of Hebei Normal University (Natural Science)
- 主办： 河北师范大学
- ISSN： 1000-5854
- CN： 13-1061/N
- 中国科技核心期刊
- 中国期刊方阵入选期刊
- 中国高校优秀科技期刊
- 华北优秀期刊
- 河北省优秀科技期刊
2-factorization of a Simple Graph Containing Triangle and Quadrilateral
摘要/Abstract
图的独立圈和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 triangles 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 sk.