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

Abdollah Khodkar; Rui Xu

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 1, page 193-204
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Abdollah Khodkar, and Rui Xu. "More on even [a,b]-factors in graphs." Discussiones Mathematicae Graph Theory 27.1 (2007): 193-204. <http://eudml.org/doc/270555>.

@article{AbdollahKhodkar2007,
abstract = {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.},
author = {Abdollah Khodkar, Rui Xu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {[a,b]-factor; spanning graph; edge-connectivity},
language = {eng},
number = {1},
pages = {193-204},
title = {More on even [a,b]-factors in graphs},
url = {http://eudml.org/doc/270555},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Abdollah Khodkar
AU - Rui Xu
TI - More on even [a,b]-factors in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 193
EP - 204
AB - 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.
LA - eng
KW - [a,b]-factor; spanning graph; edge-connectivity
UR - http://eudml.org/doc/270555
ER -

References

top
  1. [1] M.-C. Cai, On some factor theorems of graphs, Discrete Math. 98 (1991) 223-229, doi: 10.1016/0012-365X(91)90378-F. Zbl0758.05073
  2. [2] M. Kouider and P.D. Vestergaard, On even [2,b] -factors in graphs, Australasian J. Combin. 27 (2003) 139-147. Zbl1026.05092
  3. [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. Zbl1063.05109
  4. [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. Zbl1066.05110
  5. [5] L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory 8 (1970) 391-416, doi: 10.1016/S0021-9800(70)80033-3. Zbl0198.29201
  6. [6] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc, 2000). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.