no. 21-22
Combinatorics
A minimum degree condition of fractional (k,m)-deleted graphs
[Une condition sur le degré minimal pour qu'un graphe soit (k,m)-effacé fractionnaire]

Présenté par : Jean-Yves Girard

Zhou, Sizhong1
1 School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, People's Republic of China
Comptes Rendus. Mathématique, Tome 347 (2009) no. 21-22, pp. 1223-1226.

Soit G un graphe d'ordre n et k⩾1, m⩾1 deux entiers, nous notons δ(G) le degré minimal de G. Dans cette Note nous montrons que si n⩾4k−5+2(2k+1)m et δ(G)⩾n/2 alors G est un graphe (k,m)-effacé fractionnaire. De plus, nous montrons par un exemple que la condition sur le degré minimal ne peut être remplacée par δ(G)⩾(n−1)/2.

Let G be a graph of order n, and let k⩾1 and m⩾1 be two integers. In this paper, we consider the relationship between the minimum degree δ(G) and the fractional (k,m)-deleted graphs. It is proved that if n⩾4k−5+2(2k+1)m and δ(G)⩾n2, then G is a fractional (k,m)-deleted graph. Furthermore, we show that the minimum degree condition is sharp in some sense.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2009.09.022
Zhou, Sizhong 1

1 School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, People's Republic of China 
@article{CRMATH_2009__347_21-22_1223_0,
     author = {Zhou, Sizhong},
     title = {A minimum degree condition of fractional $ (k,m)$-deleted graphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1223--1226},
     publisher = {Elsevier},
     volume = {347},
     number = {21-22},
     year = {2009},
     doi = {10.1016/j.crma.2009.09.022},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2009.09.022/}
}
TY  - JOUR
AU  - Zhou, Sizhong
TI  - A minimum degree condition of fractional $ (k,m)$-deleted graphs
JO  - Comptes Rendus. Mathématique
PY  - 2009
SP  - 1223
EP  - 1226
VL  - 347
IS  - 21-22
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2009.09.022/
DO  - 10.1016/j.crma.2009.09.022
LA  - en
ID  - CRMATH_2009__347_21-22_1223_0
ER  - 
%0 Journal Article
%A Zhou, Sizhong
%T A minimum degree condition of fractional $ (k,m)$-deleted graphs
%J Comptes Rendus. Mathématique
%D 2009
%P 1223-1226
%V 347
%N 21-22
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2009.09.022/
%R 10.1016/j.crma.2009.09.022
%G en
%F CRMATH_2009__347_21-22_1223_0
Zhou, Sizhong. A minimum degree condition of fractional $ (k,m)$-deleted graphs. Comptes Rendus. Mathématique, Tome 347 (2009) no. 21-22, pp. 1223-1226. doi : 10.1016/j.crma.2009.09.022. http://www.numdam.org/articles/10.1016/j.crma.2009.09.022/

[1] Bondy, J.A.; Murty, U.S.R. Graph Theory with Applications, The Macmillan Press, London, 1976

[2] Katerinis, P. Minimun degree of a graph and the existence of k-factors, Proc. Indian Acad. Sci. Math. Sci., Volume 94 (1985), pp. 123-127

[3] Liu, G.; Zhang, L. Fractional (g,f)-factors of graphs, Acta Math. Sci., Volume 21B (2001) no. 4, pp. 541-545

[4] Liu, G.; Zhang, L. Toughness and the existence of fractional k-factors of graphs, Discrete Math., Volume 308 (2008), pp. 1741-1748

[5] Yu, J.; Liu, G.; Ma, M.; Cao, B. A degree condition for graphs to have fractional factors, Adv. Math. (China), Volume 35 (2006) no. 5, pp. 621-628

[6] S. Zhou, Z. Duan, Binding number and fractional k-factors of graphs, Ars Combin., in press

Cité par Sources :

☆ This research was supported by Jiangsu Provincial Educational Department (07KJD110048) and was sponsored by Qing Lan Project of Jiangsu Province.