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


Minimum codegree condition for perfect matchings in k-partite k-graphs
Authors:Hongliang Lu  Yan Wang  Xingxing Yu
Institution:1. School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an, China;2. School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia
Abstract:Let urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0003 be a urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0004-partite urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0005-graph with urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0006 vertices in each partition class, and let urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0007 denote the minimum codegree of urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0008. We characterize those urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0009 with urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0010 and with no perfect matching. As a consequence, we give an affirmative answer to the following question of Rödl and Ruciński: if urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0011 is even or urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0012, does urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0013 imply that urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0014 has a perfect matching? We also give an example indicating that it is not sufficient to impose this degree bound on only two types of urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0015-sets.
Keywords:k-graph  k-partite k-graph  matching  perfect matching
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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