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 条
[21]   Minimum Szeged index among unicyclic graphs with perfect matchings [J].
Liu, Hechao ;
Deng, Hanyuan ;
Tang, Zikai .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (02) :443-455
[22]   Minimum Szeged index among unicyclic graphs with perfect matchings [J].
Hechao Liu ;
Hanyuan Deng ;
Zikai Tang .
Journal of Combinatorial Optimization, 2019, 38 :443-455
[23]   On the Number of k-Matchings in Graphs [J].
Kinkar Chandra Das ;
Ali Ghalavand ;
Ali Reza Ashrafi .
Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2022, 92 :563-570
[24]   On the Number of k-Matchings in Graphs [J].
Das, Kinkar Chandra ;
Ghalavand, Ali ;
Ashrafi, Ali Reza .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES INDIA SECTION A-PHYSICAL SCIENCES, 2022, 92 (04) :563-570
[25]   An Ore-type condition for large k-factor and disjoint perfect matchings [J].
Lu, Hongliang ;
Ning, Bo .
JOURNAL OF GRAPH THEORY, 2020, 94 (03) :307-319
[26]   PACKING k-MATCHINGS AND k-CRITICAL GRAPHS [J].
Hartvigsen, David .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) :320-351
[27]   Minimum codegree threshold for (K43-e)-factors [J].
Lo, Allan ;
Markstrom, Klas .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (03) :708-721
[28]   Exact Minimum Codegree Threshold for K4--Factors [J].
Han, Jie ;
Lo, Allan ;
Treglown, Andrew ;
Zhao, Yi .
COMBINATORICS PROBABILITY & COMPUTING, 2017, 26 (06) :856-885
[29]   Aperiodicity and primitive ideals of row-finite k-graphs [J].
Kang, Sooran ;
Pask, David .
INTERNATIONAL JOURNAL OF MATHEMATICS, 2014, 25 (03)
[30]   The interplay between k-graphs and the Yang-Baxter equation [J].
Yang, Dilian .
JOURNAL OF ALGEBRA, 2016, 451 :494-525