More on even [a,b]-factors in graphs

• Autorzy: Abdollah Khodkar , Rui Xu
• Języki publikacji: EN

Abstrakty

EN

In this note we give a characterization of the complete bipartite graphs which have an even (odd) [a,b]-factor. For general graphs we prove that an a-edge connected graph G with n vertices and with δ(G) ≥ max{a+1,an/(a+b) + a - 2} has an even [a,b]-factor, where a and b are even and 2 ≤ a ≤ b. With regard to the edge-connectivity this result is slightly better than one of the similar results obtained by Kouider and Vestergaard in 2004 and unlike their results, this result has no restriction on the order of graphs.

Słowa kluczowe

EN

[a,b]-factor; spanning graph; edge-connectivity

Kategorie tematyczne

• 05C40: Connectivity

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 1
• Strony: 193-204

Daty

wydano

2007

otrzymano

2006-03-17

poprawiono

2006-07-27

Twórcy

autor

Abdollah Khodkar

• Department of Mathematics, University of West Georgia, Carrollton, GA 30118, USA

autor

Rui Xu

• Department of Mathematics, University of West Georgia, Carrollton, GA 30118, USA

Bibliografia

• [1] M.-C. Cai, On some factor theorems of graphs, Discrete Math. 98 (1991) 223-229, doi: 10.1016/0012-365X(91)90378-F.
• [2] M. Kouider and P.D. Vestergaard, On even [2,b] -factors in graphs, Australasian J. Combin. 27 (2003) 139-147.
• [3] M. Kouider and P.D. Vestergaard, Even [a,b] -factors in graphs, Discuss. Math. Graph Theory 24 (2004) 431-441, doi: 10.7151/dmgt.1242.
• [4] M. Kouider and P.D. Vestergaard, Connected factors in graphs - a survey, Graphs and Combin. 21 (2005) 1-26, doi: 10.1007/s00373-004-0587-7.
• [5] L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory 8 (1970) 391-416, doi: 10.1016/S0021-9800(70)80033-3.
• [6] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc, 2000).

Identyfikatory

DOI

10.7151/dmgt.1355