On the Perfect Matchings of Near Regular Graphs

被引:0
作者
Xinmin Hou
机构
[1] University of Science and Technology of China,Department of Mathematics
来源
Graphs and Combinatorics | 2011年 / 27卷
关键词
Perfect matching; Regular graph; Near regular graph;
D O I
暂无
中图分类号
学科分类号
摘要
Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${v \in V(G)}$$\end{document}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lfloor k/3\rfloor}$$\end{document} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lfloor k/2\rfloor}$$\end{document} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lfloor\frac{n}3\rfloor+1+(k-n)}$$\end{document} disjoint perfect matchings if h = k + 1.
引用
收藏
页码:865 / 869
页数:4
相关论文
共 7 条
  • [1] Dirac G.A.(1952)Some theorems on abstract graphs Proc. London Math. Soc. 2 69-81
  • [2] Hilton A.J.W.(1985)Factorizations of regular graphs of high degree J. Graph Theory 9 193-196
  • [3] Katerinis P.(1987)Maximum matchings in a regular graph of specified connectivity and bounded order J. Graph Theory 11 53-58
  • [4] Petersen J.(1891)Die theorie der regulären graphen Acta Math. 15 163-220
  • [5] Tutte W.T.(1947)The factorization of linear graphs J. London Math. Soc. 22 107-111
  • [6] Zhang C.Q.(1992)Factorizations of regular graphs J. Combin. Theory, Series B 56 74-89
  • [7] Zhu Y.J.(undefined)undefined undefined undefined undefined-undefined