models of random graphs

《models of random graphs》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ModelsofrandomregulargraphsN.C.WormaldSummaryThisisasurveyofresultsonpropertiesofrandomregulargraphs,to-getherwithanexpositionofsomeofthemainmethodsofobtainingtheseresults.Relatedresultsonasymptoticenumerationarealsopresented,aswellasvariousgeneralisationstorandomgraphswithgivendegreesequence

2、.Amajorfeatureinthisareaisthesmallsubgraphconditioningmethod.Whenapplicable,thisestab-lishesarelationshipbetweenrandomregulargraphswithuniformdistribution,andnon-uniformmodelsofrandomregulargraphsinwhichtheprobabilityofagraphGisweightedaccordingtothenumberofsubgraphsGhasofacertaintype.Infor-m

3、ationcanbeobtainedinthiswayontheprobabilityofexistenceofvarioustypesofspanningsubgraphs,suchasHamiltoncyclesanddecompositionsintoperfectmatchings.Uniformlydistributedlabelledrandomregulargraphsreceivemostoftheattention,butalsoincludedareseveralnon-uniformmodelswhichcomeaboutinanaturalway.Some

4、oftheseappearasspin-o®sfromthesmallsubgraphcon-ditioningmethod,andsomearisefromalgorithmswhichusesimpleapproachestogeneratingrandomregulargraphs.Aquiteseparateroleplayedbyalgorithmsisinthederivationofrandomgraphpropertiesbyanalysingtheperformanceofanappropriategreedyalgorithmonarandomregularg

5、raph.Manyopenproblemsandconjecturesaregiven.1IntroductionRandomgraphs¯rstappearedincleverprobabilisticproofsbyErd}osoftheexistenceofgraphswithspecialpropertiessuchasarbitrarilylargegirthandchromaticnumber.Thesehadnotatthattimebeenfoundconstructively.Muchlater,thestudyofrandomregulargraphstook

6、o®,beginningwiththeworksofBenderandCan¯eld[5],Bollob¶as[10]andWormald[118,117].Thishassincebeenfuelledinpartbyapplicationsinotherareassuchascomputerscience.Aninterestingapplicationoccursinbiogeography,whererandomnon-negativeintegermatriceswithgivenrowandcolumnsumsareofinterest.SeeWilson[113],

7、forexample.Thispaperisasurveyofthatpartofrandomgraphtheoryinwhichthedegreesofverticesarerestricted.Suchworkconcentratesonregulargraphsasthemostinterestingexamples,andtheresultsonregulargraphsoftenextendeasilytomoregeneraldegreesequences.Ad-re