跳圖的完美匹配和1-堅(jiān)韌度.pdf

1、YI900924碩士研究生學(xué)位論文靳疆大學(xué)論文題日(中文)：論文題目(英文)：研究生姓名：學(xué)科、專業(yè)：研究方向：導(dǎo)師姓名職稱：跳圖的完美匹配和卜堅(jiān)韌度OnPerfectMatchingsand1toughHessofJumpGraphs文4曉平基礎(chǔ)數(shù)學(xué)圖論及其應(yīng)用黃瓊湘教授論文答辯日期：2006年月目學(xué)位授予日期：2006年月日Abstraet2AbstractLinegraphsareallimportantclassoftransf

2、ormationgraphsandtheyarewidelystudiedThecomplementofalinegraphiscalledajumpgraphCom—paredwiththerichtheoryoflinegraphs，theknownresultsofjumpgraphsarepoorForasimplegraphG，WuandWang(GraphTheoryNotesofNewYork39(2000)23—25)g

3、aveanecessaryandsufficientconditionforajumpgraphJ(a)tohaveaperfectmatchingInthisthesis，wegeneralizetheresulttoalllooplessgraphs(mayhaveparalleledges)byapplyingTutte’StheoremTheproofoftheresultisbasedonthecompletecharacte

4、rizationforthestructureoftheunderlyingsimplegraphofGwhenJ(a)isnotconnectedAgraphGissaidtobe1toughifu(G—S)≤ISlforeverynonmnptypropersubsetSofy(G)，whereu(G—S)isthenumberofcomponenhsofthegraphG—SWealsogiveanecessaryandsuffi

5、cientconditionforajumpgraphJ(C)tobe1toughinthisthesisBeforestatingourmainresultslweneedsomenotationsLetCbealooplessgraph￡(G)denotesthenumberofedgesofG，A(G)denotesthemaximumdegreeofGH∈GrepresentsthatHisasubgraphofGv(a)一ma

6、xE(H)lH∈Gand旦羔凰)ifGcontainsatriangle，otherwisev(c)=0ForagraphG，anedgeeiscalledadominatingedgeifitisadjacenttoeveryotheredgeofGD(C)denotesthenumberofdominatingedgesinG∈(G)=m口zd(Ⅱ)d(“)I“andVaretakenoveranypairofadjacentver

7、ticesinG、Kidenotesthegraphobtainedfrom凰bydeletinganedge，Ktr十edenotesthegraphobtainedfromKl，byaddinganedgebetweentwoverticesofdegreesoneForanytwographsGandH，ifv(c)nV(H)=0，G日denotesthedisjointunionofGand日Thefollowingareour