Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs

被引:0
作者
Yulai Ma
Davide Mattiolo
Eckhard Steffen
Isaak H. Wolf
机构
[1] Paderborn University,Department of Mathematics
[2] KU Leuven Kulak,Department of Computer Science
来源
Combinatorica | 2024年 / 44卷
关键词
Perfect matchings; Regular graphs; Factors; -Graphs; Edge-colorings; Class 2 graphs; 05C40; 05C70;
D O I
暂无
中图分类号
学科分类号
摘要
For 0≤t≤r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0 \le t \le r$$\end{document} let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance m(3,3)=m(4,r)=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m(3,3)=m(4,r)=1$$\end{document}, and m(t,r)≤r-2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m(t,r) \le r-2$$\end{document} for all t≠5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t \not = 5$$\end{document}, and m(t,r)≤r-3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m(t,r) \le r-3$$\end{document} if r is even. We prove that m(2l,r)≤3l-6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m(2l,r) \le 3l - 6$$\end{document} for every l≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$l \ge 3$$\end{document} and r≥2l\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \ge 2 l$$\end{document}.
引用
收藏
页码:429 / 440
页数:11
相关论文
共 12 条
  • [1] Grünewald S(1999)Chromatic-index-critical graphs of even order J. Graph Theory 30 27-36
  • [2] Steffen E(2023)Pairwise disjoint perfect matchings in SIAM J. Discret. Math. 37 1548-1565
  • [3] Ma Y(2022)-edge-connected J. Graph Theory 99 107-116
  • [4] Mattiolo D(1973)-regular graphs J. Comb. Theory Ser. B 14 55-60
  • [5] Steffen E(1999)Highly edge-connected regular graphs without large factorizable subgraphs J. Graph Theory 32 1-15
  • [6] Wolf IH(1979)Regular Proc Lond Math Soc 3 423-460
  • [7] Mattiolo D(2020)-valent J. Comb. Theory Ser. B 141 343-351
  • [8] Steffen E(undefined)-connected non-Hamiltonian non undefined undefined undefined-undefined
  • [9] Meredith GHJ(undefined)-edge-colourable graphs undefined undefined undefined-undefined
  • [10] Rizzi R(undefined)Indecomposable undefined undefined undefined-undefined