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
相关论文
共 38 条
  • [11] GENERALISED MORPHISMS OF k-GRAPHS: k-MORPHS
    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 K5-Free Graphs
    Simon Straub
    Thomas Thierauf
    Fabian Wagner
    Theory of Computing Systems, 2016, 59 : 416 - 439
  • [13] Counting the Number of Perfect Matchings in K 5-Free Graphs
    Straub, Simon
    Thierauf, Thomas
    Wagner, Fabian
    THEORY OF COMPUTING SYSTEMS, 2016, 59 (03) : 416 - 439
  • [14] Perfect matchings and K1,p-restricted graphs
    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
    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
    Wenqian Zhang
    Bulletin of the Malaysian Mathematical Sciences Society, 2023, 46
  • [17] On Perfect Matchings in k-Complexes
    Han, Jie
    INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2021, 2021 (11) : 8741 - 8762
  • [18] C*-algebras associated to coverings of k-graphs
    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
    Qian Qian Liu
    He Ping Zhang
    Acta Mathematica Sinica, English Series, 2023, 39 : 1289 - 1304
  • [20] Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs
    Liu, Qian Qian
    Zhang, He Ping
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2023, 39 (07) : 1289 - 1304