On k-factor-critical graphs

Odile Favaron

Discussiones Mathematicae Graph Theory (1996)

  • Volume: 16, Issue: 1, page 41-51
  • ISSN: 2083-5892

Abstract

top
A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.

How to cite

top

Odile Favaron. "On k-factor-critical graphs." Discussiones Mathematicae Graph Theory 16.1 (1996): 41-51. <http://eudml.org/doc/270728>.

@article{OdileFavaron1996,
abstract = {A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.},
author = {Odile Favaron},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {matching; extendable; factor; perfect matching; -extendable graphs},
language = {eng},
number = {1},
pages = {41-51},
title = {On k-factor-critical graphs},
url = {http://eudml.org/doc/270728},
volume = {16},
year = {1996},
}

TY - JOUR
AU - Odile Favaron
TI - On k-factor-critical graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1996
VL - 16
IS - 1
SP - 41
EP - 51
AB - A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.
LA - eng
KW - matching; extendable; factor; perfect matching; -extendable graphs
UR - http://eudml.org/doc/270728
ER -

References

top
  1. [1] V. N. Bhat and S. F. Kapoor, The Powers of a Connected Graph are Highly Hamiltonian, Journal of Research of the National Bureau of Standards, Section B 75 (1971) 63-66. Zbl0231.05109
  2. [2] G. Chartrand, S. F. Kapoor and D. R. Lick, n-Hamiltonian Graphs, J. Combin. Theory 9 (1970) 308-312, doi: 10.1016/S0021-9800(70)80069-2. 
  3. [3] O. Favaron, Stabilité, domination, irredondance et autres parametres de graphes, These d'Etat, Université de Paris-Sud, 1986. 
  4. [4] O. Favaron, E. Flandrin and Z. Ryjáek, Factor-criticality and matching extension in DCT-graphs, Preprint. 
  5. [5] T. Gallai, Neuer Beweis eines Tutte'schen Satzes, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963) 135-139. Zbl0129.39802
  6. [6] L. Lovász, On the structure of factorizable graphs, Acta Math. Acad. Sci. Hungar. 23 (1972) 179-195, doi: 10.1007/BF01889914. Zbl0247.05156
  7. [7] L. Lovász and M. D. Plummer, Matching Theory, Annals of Discrete Math. 29 (1986). 
  8. [8] M. Paoli, W. W. Wong and C. K. Wong, Minimum k-Hamiltonian Graphs II, J. Graph Theory 10 (1986) 79-95, doi: 10.1002/jgt.3190100111. Zbl0592.05043
  9. [9] M. D. Plummer, On n-extendable graphs, Discrete Math. 31 (1980) 201-210, doi: 10.1016/0012-365X(80)90037-0. 
  10. [10] M. D. Plummer, Toughness and matching extension in graphs, Discrete Math. 72 (1988) 311-320, doi: 10.1016/0012-365X(88)90221-X. Zbl0683.05034
  11. [11] M. D. Plummer, Degree sums, neighborhood unions and matching extension in graphs, in: R. Bodendiek, ed., Contemporary Methods in Graph Theory (B. I. Wiessenschaftsverlag, Mannheim, 1990) 489-502. Zbl0745.05041
  12. [12] M. D. Plummer, Extending matchings in graphs: A survey, Discrete Math. 127 (1994) 277-292, doi: 10.1016/0012-365X(92)00485-A. 
  13. [13] Z. Ryjáček, Matching extension in K 1 , r -free graphs with independent claw centers, to appear in Discrete Math. Zbl0872.05044
  14. [14] W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947) 107-111, doi: 10.1112/jlms/s1-22.2.107. Zbl0029.23301
  15. [15] W. W. Wong and C. K. Wong, Minimum k-Hamiltonian Graphs, J. Graph Theory 8 (1984) 155-165, doi: 10.1002/jgt.3190080118. Zbl0534.05040

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.