The Existence of Even Regular Factors of Regular Graphs on the Number of Cut Edges  

作　　者：Hong Bing FAN Gui Zhen LIU Ji Ping LIU He Ping LONG 

机构地区：[1]Department of Computer Science, Wilfrid Laurier University, Waterloo, ON N2L 3C5, Canada [2]School of Mathematics, Shandong University, Ji'nan 250100, P. R. China [3]Department of Computer Science, University of Lethbridge, Lethbridge, AB., T1K 3M4, Canada

出　　处：《Acta Mathematica Sinica,English Series》2010年第12期2305-2312,共8页数学学报（英文版）

基　　金：Supported by Natural Sciences and Engineering Research Council of Canada;NNSF (Grant No. 10871119);RSDP (Grant No. 200804220001) of China

摘　　要：For any even integer k and any integer i, we prove that a （kr ＋i）-regular multigraph contains a k-factor if it contains no more than kr - 3k/2＋ i ＋ 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs.For any even integer k and any integer i, we prove that a （kr ＋i）-regular multigraph contains a k-factor if it contains no more than kr - 3k/2＋ i ＋ 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs.

关 键 词：Regular graph FACTOR cut edge 

分 类 号：O157.5[理学—数学] TQ051.84[理学—基础数学]