资源描述：
《on chromatic equivalence of graphs》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ONCHROMATICEQUIVALENCEOFGRAPHSChong-YunChaoandEarlGlenWhitehead,Jr.DepartmentofMathematicsUniversityofPittsburghPittsburgh,Pa.15260Weshowthatthecycleonnverticesandeach0-grapharechromaticallyunique.Also,weprovethatalargeclassofnonisomorphicconnectedgraphsarechromaticallye
2、quivalent.Thisclassincludesthecactusgraphs.Combinatorialidentitiesareobtainedfromthematricesconnectingchromaticpolynomialbases.IINTRODUCTIONThegraphswhichweconsiderherearefinite,undirected,simpleandloopless.TwographsXandYaresaidtobechromaticallyequivalentiftheyhavethesam
3、echromaticpolynomial,i.e.,P(X,~)=P(Y,~).AgraphXissaidtobechromaticallyuniqueifP(Y,~)=P(X,~)impliesthatYisisomorphicto~.Therearemanygraphswhicharechromaticallyequivalentandarenonisomorphic,e.g.,twononisomorphictreeswiththesamenumberofvertices.Ontheotherhand,weknowthateach
4、ofthenullgraphs,Nn,withnverticesischromaticallyunique.Soiseachofthecompletegraphs,Kn,withnvertices.Itseemsnaturaltoaskwhetherwecanfindotherfamiliesofchromaticallyuniquegraphs.Here,in§2wesh~1thatthecycle,Cn,withnverticesforn~3,andthe9-graphs,en,withnverticesforn~4arechrom
5、aticallyuniquefamiliesofgraphswhereaen,n~4,isagraphconsistsoftwocycleswithoneedgeincommon.Eachofthewheels,Wn,withnverticesforn~4seemstobechromaticallyunique.However,wecanneitherprovenordisprovethat.122OurresultsandcomputationsdependheavilyonWhitney'sreductionformulain[i~
6、andWhitney'sbrokencycletheoremin[ii].TheformulaisP(X,~)=P(X,,~)+P(x",~),orP(X',A)=P(X,A)-P(X",A)whereX'isobtainedfromXbyaddinganedgeandX"isobtainedfromXbycontractingtheendpointsoftheaddededgetoasinglevertex.LetXbeagraphwithnvertices,YbeasubgraphofXsuchthatYhassedgesandpc
7、omponents.WedefinetherankiandnullityjofYbyi=n-pandj=s-i=s-n+p.Thenp=n-iands=i+j.Letm..bethenumberofsubgraphsmjofXwithrankiandnullityj.ThenP(X,X)=E(-i)i+jxn-i=Em.~n-ii,jmijimwheremi=j2(-i)i+jmijAbrokencycleisacyclewithoutthelastedge.Whitney'sbrokencycletheoremstates:Thenu
8、mber(-l)imiisequaltothenumberofsubgraphswithiedgesinXeachofwhichdoesnotcontainalltheedgesofanybrokencyc
