首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
Authors:Shuya Chiba  Tomoki Yamashita
Institution:1. Applied Mathematics, Faculty of Advanced Science and Technology, Kumamoto University, 2-39-1 Kurokami, Kumamoto 860-8555, Japan;2. Department of Mathematics, Kindai University, 3-4-1 Kowakae, Higashi-Osaka, Osaka 577-8502, Japan
Abstract:Let G be a balanced bipartite graph of order 2n4, and let σ1,1(G) be the minimum degree sum of two non-adjacent vertices in different partite sets of G. In 1963, Moon and Moser proved that if σ1,1(G)n+1, then G is hamiltonian. In this note, we show that if k is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly k cycles for sufficiently large graphs. In order to prove this, we also give a σ1,1 condition for the existence of k vertex-disjoint alternating cycles with respect to a chosen perfect matching in G.
Keywords:2-factors  Degree conditions  Bipartite graphs  Perfect matchings  Alternating cycles
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号