The number of disjoint perfect matchings in semi-regular graphs

Applicable Analysis and Discrete Mathematics

article

Hongliang Lu¹  David G.L. Wang² 

[1] School of Mathematics and Statistics, Xi’an Jiaotong university;School of Mathematics and Statistics, Beijing Institute of Technology;Beijing Key Laboratory on MCAACI, Beijing Institute of Technology

关键词: Semiregular graph;    Hamiltonian graph;    regular graph;    perfect matching;    factorization;   

DOI  :  10.2298/AADM161109030L

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

We obtain a sharp result that for any even n ≥ 34, every {Dn, Dn+1}-regulargraph of order n contains dn/4e disjoint perfect matchings, where Dn =2dn/4e − 1. As a consequence, for any integer D ≥ Dn, every {D, D + 1}-regular graph of order n contains (D − dn/4e + 1) disjoint perfect matchings.

【 授权许可】

Unknown