3连通图的某些子图上的可去边

《3连通图的某些子图上的可去边》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文Removableedgesinsomespecialsubgraphof3·-connectedgraphsCaiYue(SchoolofMathematics，ShandongUniversity,Jinan，Shandong250100，P．R．China)ABSTRACTTheconnectivityofgraphsisoneofthemostimportantprop—ertiesofgraphs．Connectedgraphsplayanimportantroleinpracti—calapplicationsbecauseofitsclos

2、econnectionwithnetworkmodelandcombinatorialoptimization．Withtherapiddevelopmentofcom—putersandintemet，thisconnectioniSmorecloserthaneverbefore，whichmakesconnectedgraphsveryimportantinboththeoreticalre—spectandpracticalapplication．Discussingtheconstructionofcon—nectedgraphsisacuttingedgetop

3、icingraphtheory．Withinductionwidelyused，operationsingraphswhichareaseriesofalgorithmsthatreducethenumberofverticesoredgesinagraphwithkeepingsomepropertyaremoreusefuldaybyday．Inthiscontext，removableedgesandcontractibleedgesareusedinresearch．Thispaperforcusonthepropertiesofremovableedgesandc

4、on—tractibleedgesin3-connectedgraphs，andtheirdistributions．Inthispaper,Gisasimplegraph．ThefollowingarethemainresultsofthisPaper．First，wewillgiveadefinition．Considerthefollowingoperations：(1)DeleteefromG，resultinginthegraphG—e．(2)Ifsomeend—verticesofehavedegree2inG-e，thensuppressⅡI山东大学硕士学位论

5、文them．(3)Ifmultipleedgesoccur,weusesingleedgestoreplacethem．ThefinalresultantgraphisdenotedbyGee．Fora3-connectedgrahG，ifGeisstill3-connected，thentheedgeeiscalledremov—able；otherwise，itiscalledunremovable．ThesetofallremovableedgesofGisdenotedby昧(G)；whereasthesetofallunremovableedgesofGisden

6、otedbyEN(G)．Forremovableedgesin3-connectedgraphs，wewillgivesomeresults．Asfoliows：Conclusion1Gisa3-connectedgraph，Cisa6-cycleinG．Ifthereexistsatmostonesetof3verticesofdegree3，IE(C)nER(G)I≥1．Conclusion2Gisa3-connectedgraph，t，(G)≥6，Gisan-cycleinG．Ifthereexistsatmostonesetof3verticesofdegree3，

7、IE(c，1)nER(G)I≥1．Forremovableedgesoutsideaspanningtreein3-connectedgraphs，wegiveoneresultbasedontheresearchin3-regulargraph．Asfollows：Conclusion3Gisa3-connectedgraph，v(a)≥6．Iftheredosenotexistcontinuous2verticesofdegree3，thereareatleast2removableedgesoutsideas