Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (4): 123-130.

• Original Articles • Previous Articles    

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 )

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

CLC Number: