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 条
  • [21] Minimum Szeged index among unicyclic graphs with perfect matchings
    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
    Hechao Liu
    Hanyuan Deng
    Zikai Tang
    Journal of Combinatorial Optimization, 2019, 38 : 443 - 455
  • [23] On the Number of k-Matchings in Graphs
    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
    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
    Lu, Hongliang
    Ning, Bo
    JOURNAL OF GRAPH THEORY, 2020, 94 (03) : 307 - 319
  • [26] PACKING k-MATCHINGS AND k-CRITICAL GRAPHS
    Hartvigsen, David
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) : 320 - 351
  • [27] Minimum codegree threshold for (K43-e)-factors
    Lo, Allan
    Markstrom, Klas
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (03) : 708 - 721
  • [28] Exact Minimum Codegree Threshold for K4--Factors
    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
    Kang, Sooran
    Pask, David
    INTERNATIONAL JOURNAL OF MATHEMATICS, 2014, 25 (03)
  • [30] The interplay between k-graphs and the Yang-Baxter equation
    Yang, Dilian
    JOURNAL OF ALGEBRA, 2016, 451 : 494 - 525