资源描述:
《Andries E. Brouwer - Spectra of graphs》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、AndriesE.Brouwer,WillemH.HaemersSpectraofgraphs–Monograph–February1,2011SpringerPrefaceAlgebraicgraphtheoryisthebranchofmathematicsthatstudiesgraphsbyusingalgebraicpropertiesofassociatedmatrices.Moreinparticular,spectralgraphthe-orystudiestherelationbetween
2、graphpropertiesandthespectrumoftheadjacencymatrixorLaplacematrix.Andthetheoryofassociationschemesandcoherentcon-figurationsstudiesthealgebrageneratedbyassociatedmatrices.Spectralgraphtheoryisausefulsubject.ThefoundersofGooglecomputedthePerron-Frobeniuseigenv
3、ectorofthewebgraphandbecamebillionaires.Thesecondlargesteigenvalueofagraphgivesinformationaboutexpansionandrandomnessproperties.Thesmallesteigenvaluegivesinformationaboutindependencenumberandchromaticnumber.Interlacinggivesinformationaboutsubstructures.Thef
4、actthateigenvaluemultiplicitiesmustbeintegralprovidesstrongrestrictions.Andthespectrumprovidesausefulinvariant.ThisbookgivesthestandardelementarymaterialonspectrainChapter1.Importantapplicationsofgraphspectrainvolvethelargestorsecondlargestorsmallesteigen-v
5、alue,orinterlacing,topicsthatarediscussedinChapters3–4.Afterwards,specialtopicssuchastrees,groupsandgraphs,Euclideanrepresentations,andstronglyregulargraphsarediscussed.Stronglyrelatedtostronglyregulargraphsareregulartwo-graphs,andChapter10mainlydiscussesSe
6、idel'sworkonsetsofequiangularlines.Stronglyregulargraphsformthefirstnontrivialcaseof(symmetric)asso-ciationschemes,andChapter11givesaverybriefintroductiontothistopic,andDelsarte'sLinearProgrammingBound.Chapter12verybrieflymentionsthemainfactsondistance-regula
7、rgraphs,includingsomemajordevelopmentsthatoccurredsincethemonograph[51]waswritten(proofoftheBannai-Itoconjecture,construc-tionbyVanDam&KoolenofthetwistedGrassmanngraphs,determinationoftheconnectivityofdistance-regulargraphs).InsteadofworkingoverR,onecanwork
8、overFporZandobtainmoredetailedinformation.Chapter13considersp-ranksandSmithNormalForms.Finally,Chapters14and15returntotherealspectrumandconsiderinwhatcasesagraphisdeterminedbyitsspectrum,andwhenithason