资源描述：
《Extending matchings in graphs-a survey .pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、DiscreteMathematics127(1994)2777292277North-HollandExtendingmatchingsingraphs:AsurveyMichaelD.Plummer*DepartmentofMathematics,VanderbiltUniversity,Nashville,TN37240,USAReceived27November1990Revised14September1991AbstractGallaiandEdmondsindependentlyobtainedacanonicaldeco
2、mpositionofgraphsintermsoftheirmaximummatchings.Unfortunately,oneofthedegeneratecasesfortheirtheoryoccurswhenthegraphinquestionhasaperfectmatching(alsoknownasal-factor).Kotzig,Lovaszandotherssubsequentlydevelopedafurtherdecompositionofsuchgraphs.Amongtheatomsofthisde-com
3、positionisthefamilyofhicriticalgraphs.(AgraphGisbicriticalifG-u-chasaperfectmatchingforeverychoiceoftwopointsu,uinC.)Sofarsuchgraphshaveresistedfurtherdecompositionprocedures.Motivatedbythesemysteriousgraphs,weintroducedthefollowingdefinition.Letpandnbepositiveintegerswi
4、thn<(p-2)/2.GraphGisn-exrendableifGhasamatchingofsizenandeverysuchmatchingextendsto(i.e.isasubsetof)aperfectmatchinginG.Itisclearthatifagraphisbicritical,itisI-extendable.Amoreinterestingresultisthatifagraphis2-extendable,itiseitherbipartiteorbicriticai.Itisalsotruethati
5、fagraphisn-extendable,itisalso(n-I)-extendable.Hence,fornonbipartitegraphswehaveanestedsequenceoffamiliesof&criticalgraphstostudy.Inthispaper,wesurveyavarietyofresultsobtainedoverthepastfewyearsconcerningn-extendablegraphs.Inparticular,wedescribehowthepropertyofn-extenda
6、bilityinteractswithsuchothergraphparametersasgenus,toughness,claw-freedomanddegreesumsandgeneralizedneighborhoodconditions.WewillalsoinvestigatethebehaviorofmatchingextendabilityundertheoperationofCartesianproduct.Thestudyofn-extendabilityforplanargraphshasbeen,andcontin
7、uestobe,ofparticularinterest.1.Introduction,terminologyandsomemotivationForanyterminologynotdefinedinthispaper,thereaderisdirectedtoeither[23]or[3].LetGbeanyconnectedgraph.AsetoflinesMLE(G)iscalledamatchingiftheyareindependent,i.e.notwoofthemshareacommonendpoint.Amatchin
8、gissaidtobeperfectifitcoversallpointsofG.(Hereafterinthispaper,perfectmatchingCorrespondenceto:MichaelD
