Factor-criticality and matching extension in DCT-graphs

Odile Favaron; Evelyne Favaron; Zdenĕk Ryjáček

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 2, page 271-278
  • ISSN: 2083-5892

Abstract

top
The class of DCT-graphs is a common generalization of the classes of almost claw-free and quasi claw-free graphs. We prove that every even (2p+1)-connected DCT-graph G is p-extendable, i.e., every set of p independent edges of G is contained in a perfect matching of G. This result is obtained as a corollary of a stronger result concerning factor-criticality of DCT-graphs.

How to cite

top

Odile Favaron, Evelyne Favaron, and Zdenĕk Ryjáček. "Factor-criticality and matching extension in DCT-graphs." Discussiones Mathematicae Graph Theory 17.2 (1997): 271-278. <http://eudml.org/doc/270571>.

@article{OdileFavaron1997,
abstract = {The class of DCT-graphs is a common generalization of the classes of almost claw-free and quasi claw-free graphs. We prove that every even (2p+1)-connected DCT-graph G is p-extendable, i.e., every set of p independent edges of G is contained in a perfect matching of G. This result is obtained as a corollary of a stronger result concerning factor-criticality of DCT-graphs.},
author = {Odile Favaron, Evelyne Favaron, Zdenĕk Ryjáček},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {factor-criticality; matching extension; claw; dominated claw toes; claw-free graph},
language = {eng},
number = {2},
pages = {271-278},
title = {Factor-criticality and matching extension in DCT-graphs},
url = {http://eudml.org/doc/270571},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Odile Favaron
AU - Evelyne Favaron
AU - Zdenĕk Ryjáček
TI - Factor-criticality and matching extension in DCT-graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 2
SP - 271
EP - 278
AB - The class of DCT-graphs is a common generalization of the classes of almost claw-free and quasi claw-free graphs. We prove that every even (2p+1)-connected DCT-graph G is p-extendable, i.e., every set of p independent edges of G is contained in a perfect matching of G. This result is obtained as a corollary of a stronger result concerning factor-criticality of DCT-graphs.
LA - eng
KW - factor-criticality; matching extension; claw; dominated claw toes; claw-free graph
UR - http://eudml.org/doc/270571
ER -

References

top
  1. [1] A. Ainouche, Quasi claw-free graphs. Preprint, submitted. Zbl0888.05038
  2. [2] A. Ainouche, O. Favaron and H. Li, Global insertion and hamiltonicity in DCT-graphs, Discrete Math. (to appear). Zbl0958.05084
  3. [3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
  4. [4] O. Favaron, Stabilité, domination, irredondance et autres parametres de graphes (These d'Etat, Université de Paris-Sud, 1986). 
  5. [5] M. Las Vergnas, A note on matching in graphs, Cahiers Centre Etudes Rech. Opér. 17 (1975) 257-260. 
  6. [6] M.D. Plummer, On n-extendable graphs, Discrete Math. 31 (1980) 201-210, doi: 10.1016/0012-365X(80)90037-0. 
  7. [7] M.D. Plummer, Extending matchings in claw-free graphs, Discrete Math. 125 (1994) 301-308, doi: 10.1016/0012-365X(94)90171-6. 
  8. [8] M.D. Plummer, Extending matchings in graphs: A survey, Discrete Math. 127 (1994) 277-292, doi: 10.1016/0012-365X(92)00485-A. 
  9. [9] Z. Ryjácek, Almost claw-free graphs, J. Graph Theory 18 (1994) 469-477, doi: 10.1002/jgt.3190180505. Zbl0808.05067
  10. [10] Z. Ryjácek, Matching extension in K 1 , r -free graphs with independent claw centers, Discrete Math. 164 (1997) 257-263, doi: 10.1016/S0012-365X(96)00059-3. Zbl0872.05044
  11. [11] D.P. Sumner, Graphs with 1-factors, Proc. Amer. Math. Soc. 42 (1974) 8-12. Zbl0293.05157
  12. [12] D.P. Sumner, 1-factors and antifactor sets, J. London Math. Soc. 13 (2) (1976) 351-359, doi: 10.1112/jlms/s2-13.2.351. Zbl0338.05118

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.