One degree condition for graph G to be a fractional ID-(k,m)-deleted graph

Wei Gao, Yaya Wang, Zhiqun Zhang


The fractional factor problem has wide-ranging applications in areas such as network design, scheduling and the combinatorial polyhedron. A graph G is called a fractional (k, m)-deleted graph if removing any m edges from G, the resulting graph has a fractional k-factor. A graph G is also called a fractional ID-(k,m)-deleted graph if G-I is a fractional (k,m)-deleted graph for any independent set I. If m=0, then fractional ID-(k,m)-deleted graph is just fractional ID-k-factor-critical graph. In this paper, we give a result on degree condition for graph G to be a fractional ID-(k,m)-deleted graph. It is proved that a graph G is fractional ID-(k,m)-deleted graph if G has vertex number at least 6k+6m-5, minimum degree of G at least k+m+3/n and maximum degree in {dG(u), dG(v)} for each pair of non-adjacent vertices u and v at least 2n/3. We will show that the result in our paper is best possible in some sense.


Graph; Fractional k-factor; Fractional ID-k-factor-critical graph; Fractional (k,m)-deleted graph; Fractional ID-(k,m)-deleted graph

Full Text:



  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

JOS ©: World Science Publisher United States