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

被引：0
|
作者：
Hong Bing FAN Department of Computer Science
机构：
来源：
Acta Mathematica Sinica(English Series) | 2010年 / 26卷 / 12期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Regular graph; factor; cut edge;
D O I：
暂无
中图分类号：
O158 [离散数学];
学科分类号：
070104 ;
摘要：
For any even integer k and any integer i,we prove that a (kr+i)-regular multigraphcontains a k-factor if it contains no more than kr-(3k)/2+i+2 cut edges,and this result is the bestpossible to guarantee the existence of k-factor in terms of the number of cut edges.We further give acharacterization for k-factor free regular graphs.
引用
收藏
页码：2305 / 2312
页数：8
相关论文
共 50 条
  • [1] The existence of even regular factors of regular graphs on the number of cut edges
    Fan, Hong Bing
    Liu, Gui Zhen
    Liu, Ji Ping
    Long, He Ping
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2010, 26 (12) : 2305 - 2312
  • [2] 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
    Acta Mathematica Sinica, English Series, 2010, 26 : 2305 - 2312
  • [3] Cut-Edges and Regular Factors in Regular Graphs of Odd Degree
    Kostochka, Alexandr V.
    Raspaud, Andre
    Toft, Bjarne
    West, Douglas B.
    Zirlin, Dara
    GRAPHS AND COMBINATORICS, 2021, 37 (01) : 199 - 207
  • [4] Cut-Edges and Regular Factors in Regular Graphs of Odd Degree
    Alexandr V. Kostochka
    André Raspaud
    Bjarne Toft
    Douglas B. West
    Dara Zirlin
    Graphs and Combinatorics, 2021, 37 : 199 - 207
  • [5] ON THE EXISTENCE OF GENERAL FACTORS IN REGULAR GRAPHS
    Lu, Hongliang
    Wang, David G. L.
    Yu, Qinglin
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (04) : 1862 - 1869
  • [6] REGULAR FACTORS IN REGULAR GRAPHS
    KATERINIS, P
    DISCRETE MATHEMATICS, 1993, 113 (1-3) : 269 - 274
  • [7] REGULAR FACTORS OF REGULAR GRAPHS
    BOLLOBAS, B
    SAITO, A
    WORMALD, NC
    JOURNAL OF GRAPH THEORY, 1985, 9 (01) : 97 - 103
  • [8] Existence of Regular Factors in Star-free Graphs
    Kotani, Keiko
    PROCEEDINGS OF THE INTERNATIONAL CONFERENCE OF NUMERICAL ANALYSIS AND APPLIED MATHEMATICS 2014 (ICNAAM-2014), 2015, 1648
  • [9] Regular Graphs, Eigenvalues and Regular Factors
    Lu, Hongliang
    JOURNAL OF GRAPH THEORY, 2012, 69 (04) : 349 - 355
  • [10] Regular factors in regular multipartite graphs
    Hoffmann, A
    DISCRETE MATHEMATICS, 2002, 258 (1-3) : 43 - 62
12345