Minimum codegree condition for perfect matchings in k-partite k-graphs

被引:0
作者
Lu, Hongliang [1 ]
Wang, Yan [2 ]
Yu, Xingxing [2 ]
机构
[1] Xi An Jiao Tong Univ, Sch Math & Stat, Xian 710049, Shaanxi, Peoples R China
[2] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
基金
中国国家自然科学基金;
关键词
k-graph; k-partite k-graph; matching; perfect matching; UNIFORM HYPERGRAPHS; DEGREE THRESHOLDS;
D O I
10.1002/jgt.22448
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let H be a k-partite k-graph with n vertices in each partition class, and let delta(k-1) (H) denote the minimum codegree of H. We characterize those H with delta(k-1) (H) >= n/2 and with no perfect matching. As a consequence, we give an affirmative answer to the following question of Rodl and Rucinski: if k is even or n not equivalent to 2 (mod 4), does delta(k-1) (H) >= n/2 imply that H 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 (k - 1)-sets.
引用
收藏
页码:207 / 229
页数:23
相关论文
共 39 条
[11]   GENERALISED MORPHISMS OF k-GRAPHS: k-MORPHS [J].
Kumjian, Alex ;
Pask, David ;
Sims, Aidan .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2011, 363 (05) :2599-2626
[12]   Counting the Number of Perfect Matchings in K 5-Free Graphs [J].
Straub, Simon ;
Thierauf, Thomas ;
Wagner, Fabian .
THEORY OF COMPUTING SYSTEMS, 2016, 59 (03) :416-439
[13]   Counting the Number of Perfect Matchings in K5-Free Graphs [J].
Simon Straub ;
Thomas Thierauf ;
Fabian Wagner .
Theory of Computing Systems, 2016, 59 :416-439
[14]   Perfect matchings and K1,p-restricted graphs [J].
Irzhavski, Pavel A. ;
Orlovich, Yury L. .
DISCRETE MATHEMATICS AND APPLICATIONS, 2020, 30 (06) :391-408
[15]   The spanning k-trees, perfect matchings and spectral radius of graphs [J].
Fan, Dandan ;
Goryainov, Sergey ;
Huang, Xueyi ;
Lin, Huiqiu .
LINEAR & MULTILINEAR ALGEBRA, 2022, 70 (21) :7264-7275
[16]   Spectral Conditions for Connectivity, Toughness and perfect k-Matchings of Regular Graphs [J].
Wenqian Zhang .
Bulletin of the Malaysian Mathematical Sciences Society, 2023, 46
[17]   On Perfect Matchings in k-Complexes [J].
Han, Jie .
INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2021, 2021 (11) :8741-8762
[18]   C*-algebras associated to coverings of k-graphs [J].
Kumjian, Alex ;
Pask, David ;
Sims, Aidan .
DOCUMENTA MATHEMATICA, 2008, 13 :161-205
[19]   Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs [J].
Liu, Qian Qian ;
Zhang, He Ping .
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2023, 39 (07) :1289-1304
[20]   Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs [J].
Qian Qian Liu ;
He Ping Zhang .
Acta Mathematica Sinica, English Series, 2023, 39 :1289-1304