廣義Petersen圖和循環(huán)圖的羅馬支配研究.pdf

1、大連理工大學碩士學位論文廣義Petersen圖和循環(huán)圖的羅馬支配研究姓名：吉春年申請學位級別：碩士專業(yè)：計算機軟件與理論指導教師：林曉惠20081218大連理工大學碩士學位論文ResearchonRomanDominationinGeneralizedPetersenGraphandCirculantGraphAbstractRomanproblemisalocationproblemwhichapproachedbytheEmpero

2、rConstantineinthe4thcenturyInthe3rdcentury，whenRomedominatedEurope，itwasabletodeploy50legionsthroughouttheempire，securingeventhefurthermostareasBythefollowingcenturytheempirehadlostmuchofitsmuscle，however，andRome。Sforces

3、haddiminishedtojust25legionsSo，howtodefendtheRomanEmpirefrommultipleattacksbystationingasfewlegionsaspossiblewillbethemostimportantproblemReVellesuggestedRomandominationin1997，afewyearsearlierStewartandReVellegivethedefi

4、nitionofRomandominationwithgraphtheoryin1999ForagraphG=(y，E)，letf：V一01，2)，andlet(z0，巧，砭)betheorderedpartitionofVinducedbyf，where杉=1，∈vlf(v)=i)andf杉l=nf，fori=01，2Afunctionf=(％，K，砭)isaRomando‘minatingfunction(RDF)if％domina

5、tesv0，ie圪v0Andtheweightoffisf(V)=∑創(chuàng)廠(V)=2n2刀1TheminimumweightofallRDFofGiscalledtheRomandominationnumberofG，denotedby‰(G)，andwesaythatafunctionf=(v0，K，％)isa7尺一functionifitisanRDFand廠(礦)=y只(G)Inthispaper，、)~，iththealgorit

6、hmofcalculatingtheromandominationnumberofgraphs，westudytheromandominationnumberofgeneralizedPetersengraphsP(n，后)andcirculantgraphsC(咒；1，后))andthengetthefollowingconclusions(1)爍㈣％2))：l等b≥5)m卜㈨)))槲Qm嘶1，4))∈憎z4nII脅4nLIII]J，

7、k(cO；1，4))∈IIiiIll，LI，，f=07orn=6，12，13，19，26，30，32，F(xiàn)orgeneralizedPetersengraphsP(n，k)andcirculantgraphsC(，z；l，尼))，theupperboundsoftheirromandominationnumbersaregivenKeyWords：RomanDomination；DominationNumber；DominatingSet