资源描述:
《algebraic_graph_theory(习题提示)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、ThisreportissubmittedforcreditforMATHS783,semesterII2004.Name:RobinChristianStudentID:2376183Supervisor:DrPaulBonningtonAlgebraicGraphTheoryChrisGodsil&GordonRoyleDuringthecourseofthissemesterIhavereadchapters(1),(2),3,4,5,(8),12,13and15ofAlgebraicGraphTheorybyChrisGo
2、dsilandGordonRoyle.Thechaptersinbracketswererevisionorintroductorymaterial.Briefly,thecontentofeach(important)chapterwas:Chapter3:Propertiesofvertex-transitiveandedge-transitivegraphs,connectivityoftransitivegraphs,matchings,Hamiltonpaths&cycles.Chapter4:Arc-transitiv
3、eanddistance-transitivegraphs,s-arcregularity,theCoxetergraphandTutte’s8-cage.Chapter5:Partiallinearspaces,generalizedpolygons,Mooregraphs,theHoffman-Singletongraph.Chapter12:Generalizedlinegraphs,thecharacterizationofallgraphswithminimumeigenvalueatleast-2usingrootsy
4、stems.Chapter13:TheLaplacianofagraph,countingspanningtrees,representations,resultsonthesecond-lowesteigenvalueoftheLaplacian,interlacing,conductance.Chapter15:Matroidsandtheirrelationshipwithgraphsandcodes,therankpolynomial,deletion-contraction.Thisreportconsistsofhin
5、tsforselectedexercisesfromeachofthesechapters.MostoftheexercisesIcompletedareincludedhere,althoughIleftout“semi-proved”exercises,andafew(mostofthesewerefromChapter13)whereIhadacompleteproofbutIcouldnotfindawaytohintatorsummarizethesolutionconcisely.Scribbledversionsof
6、theseproofsareinthenoteshandedinwiththisreport.Ihaveindicatedsomeofmyfavouriteexerciseswitha*.Inafewplacesmynotationdiffersfromthatofthetext.Ihaveusedx·yfortheinnerproductofxandyinsteadof,radiansinsteadofdegrees,A+BfortheunionofsetsAandB,andA*BfortheCartesianprod
7、uctofgraphsAandB.HintsonSelectedExercisesChapter31.LabeltheverticesoftheoriginalK5intheconstruction{1,2,3,4,5}clockwise,andthe‘duplicate’vertexi’foreachi.Labelthe“edge”vertexconnectedtoi,j,i’andj’asij.ThenlabeltheverticesinFigure3.2{14,25,13,24,35,45,34,23,12,15}downt
8、hemaindiagonaland{1,2,3,4,5,5’,4’,3’,2’,1’}downthesecondarydiagonal.Itshouldbeclearthatthisprovidesanisomorphism,andalsothat