A Variety of Conjectures on Cayley Graphs Generated by Connected Graphs

《A Variety of Conjectures on Cayley Graphs Generated by Connected Graphs》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AVarietyofConjecturesonCayleyGraphsGeneratedbyConnectedGraphsHaizhongShi1⋆andYueShi21CollegeofMathematicsandStatistics,NorthwestNormalUniversity,Lanzhou,GansuProvince,730070,P.R.China2ResearchCenterofBigData&GraphTech,Lanzhou,GansuProvince,730070,P.R.C

2、hinaAbstract.Conjecture:LetG=(V,E)beaconnectedgraphwithn(3)nodesandmedges.Ifm=2r,thentheCayleygraphgeneratedbyGbetheunionofk(0kr)edge-disjointHamiltoniancyclesandm2kperfectmatchings;ifm=2r+1,thentheCayleygraphgeneratedbyGbetheunionofk(0kr)edge-di

3、sjointHamiltoniancyclesandm2kperfectmatchings.Inparticular,fork=randstargraph,theconjecturewasproposedbyHai-zhongShiin1998.Keywords:Cayleygraph,transpositiongraph,Hamiltoniancycle,con-jecture,perfectmatching1IntroductionCayleygraphgeneratedbyconnected

4、graphwasproposedtodesigncertainin-terconnectionnetworksforsupercomputers/on-chipinterconnectionnetworks/datacenternetwork[1-4].In1998and2008,etc,references[3-8]proposedmanyconjecturesregardingcertaininterconnectionnetworksincludingstarnetwork,bubblesor

5、tnetworkandCayleygraphgeneratedbytranspositiontree,etc.Thesepapers[3-8]widelydrewresearchers'attention,butnoneofthoseconjectureshavebeensolvedsofar.Aftersixteenyears'innerponderationandexplorationregardingCayleygraphgeneratedbyconnectedgraph,weproposed

6、astrongerconjectureinthispaper.Thisconjecturenotonlyuniedtheaboveconjecturesinreference[3-8](thatisifthisconjectureistrue,thenalltheaboveconjecturesaretrue),butalsohadamoregeneralmeaning,whichmeanthattheaboveconjecturesinreference[3-8]areonlyspecialci

7、rcumstancesofthisconjecture.Byproposingthisconjecture,wehopeitwillplayanimportantroleinbothdesigninginterconnectionnetworksandpromotingcertaintheoreticalresearchesregardingthesespecicCayleygraphs.Letn3andGbeaconnectedgraphwithnodesetf1;2;:::;ngandedg

8、esetE(G)wherejE(G)j=m.LetSnbethesymmetricgrouponf1;2;:::;ng.T(G)=f(ij)j(ij)isatranspositionofSnand(i;j)2E(G)g.Fromreferences[1,2],T(G)isageneratingsetofSn.CayleygraphCay(Sn;T(G))iscalledCayley⋆Correspondingauthor2HaizhongShi,YueShigraph