English

运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 123-130.

• 运筹学 • 上一篇    

分数k-因子临界图的条件

李巧1, 刘岩1,*   

  1. 1.  华南师范大学数学科学学院, 广州 510631
  • 出版日期:2013-12-15 发布日期:2013-12-15
  • 通讯作者: 刘岩 E-mail:liuyan@scnu.edu.cn

Conditions of a graph being fractional k-factor-critical

LI Qiao1, LIU Yan1,*   

  1. 1. School of Mathematical Science, South China Normal University, Guangzhou 510631,  China
  • Online:2013-12-15 Published:2013-12-15
  • Supported by:

    Supported by the National Natural Science Foundation of China (No. 11061027 )

PDF

580

被引次数

1

摘要： 设G是一个连通简单无向图，如果删去G的任意k个顶点后的图有分数完美匹配，则称G是分数k-因子临界图. 给出了G是分数k-因子临界图的韧度充分条件与度和充分条件，这些条件中的界是可达的，并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件.

关键词: 分数完美匹配, 分数k-因子临界图, 韧度, 分数匹配数

Abstract: Let G be a connected undirected simple graph. If the remaining subgraph still has a fractional perfect matching after deleting any k vertices of G, the graph G is said to be fractional k-factor-critical. This paper gives sufficient conditions in terms of the toughness and the degree sum for a graph G to be fractional k-factor-critical. In some sense, we prove that the conditions are best possible. Besides, we give a necessary and sufficient condition in terms of the fractional matching number for a graph G  to be fractional k-factor-critical.

Key words: fractional perfect matching, fractional k-factor-critical, toughness, fractional matching number

中图分类号: