數(shù)學(xué)外文+中文翻譯

SIAMJ.DISCRETEMATH.Vol.26,No.1,pp.193–205ROMANDOMINATIONON2-CONNECTEDGRAPHS?CHUN-HUNGLIU?ANDGERARDJ.CHANG?Abstract.ARomandominatingfunctionofagraphGisafunctionf:V(G)→{0,1,2}suchthatwheneverf(v)=0,thereexistsavertexuadjacenttovsuchthatf(u)=2.Theweightoffisw(f)=.TheRomandominationnumberofGistheminimumweightofaRomandominatingfunctionofGChambers,Kinnersley,Prince,andWest[SIAMJ.DiscreteMath.,23(2009),pp.1575–1586]conjecturedthat≤[2n/3]forany2-connectedgraphGofnvertices.Thispapergivescounterexamplestotheconjectureandprovesthat≤max{[2n/3],23n/34}forany2-connectedgraphGofnvertices.Wealsocharacterize2-connectedgraphsGforwhich=23n/34when23n/34>[2n/3].Keywords.domination,Romandomination,2-connectedgraphAMS.subjectclassifications.05C69,05C35DOI.10.1137/0807330851.Introduction.ArticlesbyReVelle[14,15]intheJohnsHopkinsMagazinesuggestedanewvariationofdominationcalledRomandomination;seealso[16]foranintegerprogrammingformulationoftheproblem.Sincethen,therehavebeenseveralarticlesonRomandominationanditsvariations[1,2,3,4,5,7,8,9,10,11,13,17,18,19].EmperorConstantineimposedtherequirementthatanarmyorlegioncouldbesentfromitshometodefendaneighboringlocationonlyiftherewasasecondarmywhichwouldstayandprotectthehome.Thus,therearetwotypesofarmies,stationaryandtraveling.Eachvertex(city)thathasnoarmymusthaveaneighboringvertexwithatravelingarmy.Stationaryarmiesthendominatetheirownvertices;avertexwithtwoarmiesisdominatedbyitsstationaryarmy,anditsopenneighborhoodisdominatedbythetravelingarmy.Inthispaper,weconsider(simple)graphsandlooplessmultigraphsGwithvertexsetV(G)andedgesetE(G).Thedegreeofavertexv∈V(G)isthenumberofedgesincidenttov.NotethatthenumberofneighborsofvmaybelessthandegGvinalooplessmultigraph.ARomandominatingfunctionofagraphGisafunctionf:V(G)→{0,1,2}suchthatwheneverf(v)=0,thereexistsavertexuadjacenttovsuchthatf(u)=2.Theweightoff,denotedbyw(f),isdefinedas.ForanysubgraphHofG,letw(f,H)=.TheRomandominationnumberofGistheminimumweightofaRomandominatingfunction.Amongthepapersmentionedabove,wearemostinterestedintheonebyChambersetal.[2]inwhichextremalproblemsofRomandominationarediscussed.Inparticular,theygavesharpboundsforgraphswithminimumdegree1or2andboundsof+and.Aftersettlingsomespecialcases,theygavethefollowingconjectureinanearlierversionofthepaper[2].Conjecture(Chambersetal.[2]).Forany2-connectedgraphGofnvertices,≤[2n/3]。Thispaperprovesthat≤max{[2n/3],23n/34}forany2-connectedgraphGofnvertices.Noticethat23n/34islargerthan2n/3byn/102.Wealsocharacterize2-connectedgraphsGwith=23n/34when23n/34>[2n/3].ThiswasinfactsuspectedbyWestthroughaprivatecommunicationandprovedaftersomediscussionswithhim.2.Counterexamplestotheconjecture.Inthissection,wegivecounterexamplestotheconjecturebyChambersetal.[2].TheexplosiongraphofalooplessmultigraphGisthegraphwithvertexsetV()=V(G)∪{,,,,:e=xy∈E(G)}andedgesetE)={x,y,,,,,e:e=xy∈E(G)};seeFigure1.Noticethat{,,,}inducesa5-cyclein,denotedbyCe.Wecall,,theinnerverticesofCeandof.NotethatevenifGhasparalleledges,itsexplosiongraph,isasimplegrapTheorem1.Thereareinfinitelymany2-connectedgraphswithRomandominationnumberatleast23n/34,wherenisthenumberofverticesinthegraph.Proof.Considerkgraphs,,...,,eachisomorphicto,andtheirexplosiongraphs,,...,.LetGbea2-connectedgraphobtainedfromthedisjointunionoftheseexplosiongraphs’sbyaddingsuitableedgesbetweenverticesoftheoriginalgraphss;i.e.,theseaddededgesandthesforma2-connectedgraph.Then,Ghasn=34kvertices.Weclaimthat≥23n/34=23k.Supposetothecontrarythat<23k.ChooseanoptimalRomandominatingfunctionfofG.Since=w(f)<23k,thereissomewithw(f,)<23.Noticethatforanyedgexyin,nomatterwhatthevaluesoff(x)andf(y)are,itisalwaysthecasethatw(f,)≥3.Furthermore,iff(x)≤1andf(y)≤1,theninfactw(f,)≥4.Supposehasrverticesvwithf(v)≤1,where0≤r≤4.Therearethen〔〕edgesxyinwithw(f,)≥4.Thus23>w(f,)≥r·0+(4?r)2+6·3+〔〕or,equivalently,2r>3+〔〕,whichisimpossibleas0≤r≤4.Thelowerbound23n/34inthetheoremaboveisinfacttheexactvalueforthegivengraphG.Thiswillbeseenfromthefollowingtheorem,whoseproofemploysamethodthatisusefulintheentirepaper.Fortechnicalreasons,weoftenconsiderthreeRomandominatingfunctions,,and.Weusetodenotethe3-tuple(,,),and(v)for((v),(v),(v)).Theweightofisw()=.Notethatw()≤w()/3forsomej.Avertexvis-strongif(v)=2forsomej.Theorem2.IfistheexplosiongraphofalooplessmultigraphGwithoutisolatedverticesandhasvertices,thenhasa3-tupleofRomandominatingfunctionssuchthatw()≤69/34andeverynoninnervertexis-strong.Furthermore,ifsuchsatisfiesw()=69/34,thenGisadisjointunionof’s.Proof.IfGhasnverticesandmedges,then=n+5m.Weshallconstructbyfirstassigningvalues0,1,or2totheverticesinG.Forthispurpose,weordertheverticesofGinto,,...,andletbethesubgraphofGinducedby{,...,}asfollows.Noticethat=G.Startingfromi=n,dothefollowingloop:ifGihasavertexofdegreenotequalto3oravertexofdegree3thathasatmosttwoneighbors,thenchooseitasvi;otherwisechooseavertexofdegree3asvianditsthreeneighborsas,,.Fortheformercase,let=andthenreplaceibyi?1torepeattheloop;forthelattercase,let=fork=i,i?1,i?2,i–3andthenreplaceibyi?4torepeattheloopEveryedgeofGservesasa“backedge”ofsome,i.e.,withi>k.Hence,m=。Once()hasbeendefinedfork<isuchthat()=2forsomewedefine()with()=2forsomeaccordingtothefollowingcases.WecallanedgexyofGatype-1edgeforif(x)≤1and(y)≤1;otherwiseitisatype-2edgefor.Inthefollowing,weshallcounteveryedgeofGthreetimesasatype-1oratype-2edgeforthrees.Case1.≥4.Inthiscase,let()=(2,2,2).Then,noneofthebackedgesofiscountedasatype-1edgeforsomes.Also,=1asdesired.Case2.≤2or=3,buthasatmosttwoneighbors.Inthiscase,thereissomesuchthatforanybackedgeof.Define()=2and()=0forallj.Thebackedgesofarecountedastype-1edgesforsomes.foratmosttimes.Case3.=3fori≤≤i+3,whereisabackedgeoffori≤≤i+2.Inthiscase,≤2fori≤≤i+2and=3.Fori≤≤i+3,similartoCase2,wemaychoosesome.foratleastmin{2,}backedgesof.Define()=2and()=0forallj.Thebackedgesofarecountedastype-1edgesforsomesforatmosttimesifi≤i’≤i+2andforatmost4=1+timesifi’=i+3.So,for,+1,+2,vi+3,thebackedgesarecountedastype-1edgesforsomeforatmost1+times,where≥6.Now,wehaveassignedvalues(v)suchthatvis-strongforallverticesvinG.Wethenassignvaluesforverticesinall,wheree=xy,asSinceGhasnoisolatedvertex,,,andareRomandominatingfunctionsof.Foredgesxywhicharetype1forsomeinG,()=()=2;foredgesxywhicharetype2forallinG,sincetherearesuchthat(x)=(y)=2,wehave()=()=2andsoandare-strong.Next,wecalculatew().SupposethattherearecindicesisuchthatGiissimpleand3-regular,asinCase3.Then,4c≤nand6c≤:isinCase3}≤m.Thesegivethat34c≤n+5m=n’andsoc≤n’/34.Thus,wehaveFurthermore,whenw()=69n’/34,cmustbeequalton’/34andhence6c=:isinCase3}=m,whichmeansthatCases1and2hadneverhappened.Bythealgorithmofordering{,,...,}describedatthebeginningoftheproof,Gmustbeadisjointunionof’s.Thiscompletestheproofofthetheorem.3.Romandominationon2-connectedgraphs.Inthissection,weestablish ourmainresultfortheRomandominationon2-connectedgraphs.Theorem3.Forany2-connectedgraphGofnvertices,≤max{[2n/3],23n/34}.Furthermore,if23n/34>[2n/3]andGcontainsnospanningsubgraphisomorphictotheexplosiongraphofadisjointunionofK4’s,then<23n/34.Proof.SupposetothecontrarythatthetheoremisfalseandGisaminimumcounterexampletothetheorem.Inotherwords,Gisa2-connectedgraphofordernwith>max{[2n/3],23n/34},andany2-connectedgraphoforderwith+|E()|<n+|E(G)|satisfiesγR()≤max{[2n/3],23/34}.Inparticular,Gisaminimally2-connectedgraph.AccordingtoLemma4,wehavethefollowingclaim.Claim1.Gdoesnothaveacyclewithachord.Lemma4(Dirac[6],Plummer[12]).A2-connectedgraphisminimally2-connectedifandonlyifeverycycleisaninducedcycle.Acycleispendentifithasnochordsandallofitsverticesexceptexactlytwononadjacentverticesareofdegree2.Claim2.Anytwopendent5-cyclesinGarevertex-disjointProof.SupposetothecontrarythatGhastwopendent5-cyclesandthatarenotvertex-disjoint.Let=and,bethetwoverticesofdegreeatleast3fori=1,2,where=andpossibly=.WenowconsiderthegraphobtainedfromthesubgraphofGinducedbyV(G)?{:i=1,2,j=2,4,5}byaddingedgesand.Itisclearthatisa2-connectedgraphwith=n?6verticesand|E()|<|E(G)|.BytheminimalityofG,wehaveγR()≤max{[2/3],23/34}.ChooseaRomandominatingfunctionofwithw()=γR().DefinefunctiongonV(G)byg(v)=(v)forallv∈V(C1∪C2)andfori=1,2.ThengisaRomandominatingfunctionofGwithw(g)≤w()+4.ThisgivesγR()≤max{[2n/3],23n/34},acontradictiontothechoiceofG.Noticethateachpendent5-cycleinGcanbeextendedtoanexplosiongraphofBut,puttingthemtogetherisnotnecessarilyanexplosiongraph,asavertexinsomependent5-cyclemaypossiblybethevertexofanexplosiongraphofK2whichisextendedfromanotherpendent5-cycle.However,thefollowinglemmawillproduceanexplosiongraphthatoverlapsallpendent5-cyclesinGbychoosingSastheemptyset.Lemma5.LetHbeagraphinwhichanytwopendent5-cyclesarevertex-disjoint,andletSbeasubsetofV(H).Ifeverypendent5-cycleCofHisadjacenttoatleasttwoverticesinH?V(C),thenHhasasubgraphLisomorphictotheexplosiongraphofalooplessmultigraphwithoutisolatedverticessuchthatnopendent5-cyclesinHarevertex-disjointfromS∪V(L),buteverypendent5-cycleinLisvertex-disjointfromS.Proof.SupposethatHhaskpendent5-cycles,,...,whicharevertexdisjointfromS,whereandarethetwoverticesofdegreeatleast3offoralli.Weshallprovethelemmabyinductiononk.Thelemmaisclearfork=0.Supposenowthatk≥1.ConstructanauxiliarydigraphFwithV(F)={}andE(F)={∈E(H):hasdegree3inH}.Theneachhasindegree≤1,and=1impliestheoutdegree≤1.Hence,thereisatleastanindexrwith≤1and≤1.Forotherwise,foreachi,either≥2or≥2,andsoeither=0ordeg?Dvi,3=0.Theformerimpliesthat|E(F)|=≥2k,whilethelatterimpliesthat|E(F)|=≤k<2k,acontradiction.Forj=1,3,sincethereareatleasttwoverticesinH?V()adjacentto(,wemaychooseaneighborofinV(H)\V()suchthat=.Then,togetherwiththeedgesandisanexplosiongraphofanedge.LetbethegraphobtainedfromHbydeletingalledgesof,andletbeS∪{}.ThenisasubsetofV(),andeverypendent5-cycleofwhichisvertex-disjointfrommustbeapendent5-cycleofHwhichisvertex-disjointfromS.Inparticular,Crisnotin.Bytheinductionhypothesis,hasasubgraphisomorphictotheexplosiongraphofalooplessmultigraphwithoutisolatedverticessuchthatnopendent5-cyclesofarevertex-disjointfrom∪V(),buteverypendent5-cycleinisvertex-disjointfrom.ThenL:=∪isasubgraphofHasdesired.GivenasubgraphLofG,avertexinLiscalledaboundary(respectively,interior)vertexwithrespecttoGifitisadjacenttosome(respectively,no)vertexinV(G)?V(L).Avector(,,...,)islex-largerthananothervector(,,...,)ifthereissomejsuchthat>and>foralli<j.AccordingtoLemma5(bychoosingSastheemptyset)andTheorem2,GhasasubgraphLofverticessatisfyingcondition(M)andGcontainsnopendent5-cycleswhicharevertex-disjointfromV(L).WemayassumethatLischosensothat(,|E(L)|)islex-maximum(M)Thereisa3-tupleofRomandominatingfunctionsofLwhoseboundaryverticeswithrespecttoGare-strongandw(,L)≤max{2+2,69/34}.Furthermore,if69/34>2+2andw(,L)=69/34,thenLhasaspanningsubgraphisomorphictotheexplosiongraphofadisjointunionof.NotethatLisaninducedsubgraphofG,asaddingedgespreservescondition(M).WeshallderiveacontradictionfromthefactthatGL.ItispossiblethatLisempty,asGmaycontainnopendent5-cycle.Inthatcase,weapplyLemma6togetanonemptyLLemma6.Ift≥3,thenthet-cycleCthasa3-tupleofRomandominatingfunctionsinwhichallverticesare-strongandw()≤2twhentisamultipleof3andw()≤2t+2otherwiseProof.SupposeV()={,,...,}andE(Ct)={,,...,,,}.Forthecasewhent=3p,thefollowingisasdesired:(v3i+1)=(2,0,0),(v3i+2)=(0,2,0),and(v3i+3)=(0,0,2)foralli.Forthecasewhent=3p+1(respectively,t=3p+2),theabovewiththefollowingmodificationisasdesired:(v1)=(2,0,1)and(vt)=(2,1,0)(respectively,(v1)=(2,0,2)).Claim3.LisnotemptyProof.IfGcontainspendent5-cycles,thentheclaimfollowsfromLemma5andTheorem2;otherwisetheclaimfollowsfromLemma6andthefactthata2-connectedgraphhasacycleToestablishmorepropertiesforL,wealsoneedthefollowinglemmaLemma7.SupposeHhasa3-tupleofRomandominatingfunctionsforwhichuandvare-strong,say(u)=2and(v)=2.IfisobtainedfromHbyaddingadisjointpathP=...witht≥1andtwoedgesuandV,thencanbeextendedtosuchthatw(,P)=2tandis-strongfor1<i<t.Furthermore,andarealso-strongift2(mod3)withjkort2(mod3)withj=k.Proof.Weshalldefineas()=(2,0,0),()=(0,2,0),and()=(0,0,2)foralliwithsomemodificationsaccordingtothevalue(tmod3)andwhetherj=kornotinfollowingsixcasesCase1.t≡0(mod3)andj=k,sayj=k=1.Inthiscase,change()from(2,0,0)to(0,0,1)and(v2)from(0,2,0)to(1,2,0)asfollows.Case2.t≡0(mod3)andjk,sayj=3andk=1.Inthiscase,nomodificationisneededCase3.t≡1(mod3)andj=k,sayj=k=1.Inthiscase,ift=1,thenchange(v1)from(2,0,0)to(0,1,1)asfollows.Asfort1,change()from(2,0,0)to(0,0,1),()from(0,2,0)to(1,2,0),()from(0,0,2)to(1,0,2),and()from(2,0,0)to(0,1,0)asfollows.Case4.t≡1(mod3)andjk,sayj=3andk=2.Inthiscase,nomodificationisneededCase5.t≡2(mod3)andj=k,sayj=k=3.Inthiscase,nomodificationisneeded.Case6.t≡2(mod3)andjk,sayj=1andk=3.Inthiscase,change()from(2,0,0)to(0,0,1)and()from(0,2,0)to(1,2,0)asfollows.The3-tupleisthenasdesired.Claim4.Lisconnected.Proof.IfLisnotconnected,thenwecanchoosetwocomponentsofLandapathPinG?V(L)withoneendpointadjacenttoavertexinacomponentandtheotherendpointadjacenttoavertexintheothercomponent.AccordingtothelengthofP,wecaninterchangetheroleofinacomponentsothatwecanapplythelaststatementofLemma7toextendtoL∪PsuchthatallverticesofPandallboundaryverticesofL∪Pare-strong.Thiscontradictsthelex-maximalityofL.NextarefourpropertiesofG?V(L),whichalsofollowfromLemmas6and7.Claim5.G?V(L)containsno3p-cycleforanypositiveintegerp.Claim6.G?V(L)containsnopathwhoseendpointsareadjacenttoverticesinLandareinteriorverticesofL∪PwithrespecttoG.Claim7.G?V(L)containsnopathP=...witht=3por3p+1forsomepositiveintegerpsuchthatthereexistu,v∈Landdistincti,j∈{1,2,3}withU,V∈E(G)and(u)=(v)=2.Claim8.G?V(L)containsnopathP=...witht=3p+2forsomepositiveintegerpsuchthatthereexistu,v∈LwithU,V∈E(G)and(u)=(v)=2forsomei∈{1,2,3}.ForfurtherpropertiesofG?V(L),weneedtwomorenotions.First,atailedt-cycleHisacycle.....togetherwithapath...calledthetailandanedge.Wecallu1thestartingvertexandtheinnervertexofH.

SIAMJ.離散數(shù)學(xué).第26卷,第一期,頁193–2052-連通圖的Roman控制數(shù)劉春掛?和杰拉德?j?張?文摘.一個(gè)Roman控制函數(shù)的一個(gè)圖G是一個(gè)函數(shù)f:V(G)→{0,1,2}這樣每當(dāng)f(v)=0,存在一個(gè)頂點(diǎn)u與相鄰的v這樣f(u)=2.f的重量w(f)=。Roman控制數(shù)是由Chambers,Kinnersley,Prince提出G的最小重量Roman控制函數(shù)G。和西[SIAMJ..離散數(shù)學(xué)。,23(2009),頁1575-1586)中推測2-連通圖G的n頂點(diǎn)。給出了反例的猜測,證明≤max{[2n/3],23n/34}任何2-連通圖G的n頂點(diǎn)。我們還描述2-連通圖G的=23n/34當(dāng)23n/34>[2n/3]。關(guān)鍵詞.控制數(shù)，Roman控制數(shù)，2-連通圖主題分類.05C69,05C35識(shí)別號(hào).10.1137/0807330851.推廣.文章由雷維爾(14、15)在約翰霍普金斯大學(xué)雜志建議一個(gè)新的變化稱為Roman控制支配;參見[16]一個(gè)整數(shù)規(guī)劃模型的問題。從那時(shí)起,有幾篇文章在Roman控制和它的變體(1、2、3、4、5、7、8、9、10、11、13、17、18、19)。皇帝康斯坦丁強(qiáng)加的要求軍隊(duì)或軍團(tuán)能被派從外鄉(xiāng)保衛(wèi)一個(gè)鄰近的位置只有如果有第二軍保持和保護(hù)家庭。因此,有兩種類型的軍隊(duì),靜止和旅行。每個(gè)頂點(diǎn)(城市),沒有軍隊(duì)必須有一個(gè)相鄰的頂點(diǎn)與旅游軍隊(duì)。固定的軍隊(duì)然后主宰自己的頂點(diǎn),頂點(diǎn)和兩個(gè)軍隊(duì)主要由其固定軍隊(duì),其開放的社區(qū)是由旅游軍隊(duì)。在本文中,我們考慮(簡單的)圖形和looplessmultigraphsG與頂點(diǎn)集V(G)和邊集E(G)。程度的一個(gè)頂點(diǎn)v∈v(G)是邊數(shù)事件v。注意數(shù)量的相鄰的v可能會(huì)比在一個(gè)looplessmultigraphs。一個(gè)Roman控制函數(shù)的一個(gè)圖G是一個(gè)函數(shù)f：V(G)→{0、1、2}這樣每當(dāng)f(V)=0,存在一個(gè)頂點(diǎn)u相鄰的V這樣f(u)=2。的重量,用w(f),被定義為。對于任何子圖HG,讓w(f、H)=。Roman控制數(shù)的數(shù)量G是最低重量的羅馬控制函數(shù)。在文獻(xiàn)中提到的,我們最感興趣的一個(gè)空間etal.[2]中極值問題討論的Roman控制。特別是,他們給了鋒值的邊界圖1或2與最低的程度和范圍+and。解決后,一些特殊的情況下,他們給了以下猜測在早先版本的論文[2]。猜測(Chambersetal.[2])。對于任何2-連通圖G的n頂點(diǎn),≤[2n/3]。本文證明≤max{[2n/3],23n/34}，任何2-連通圖G的n頂點(diǎn)。注意,23n/34是大于2n/3和n/102。我們還描述2-連通圖G=23n/34當(dāng)23n/34>[2n/3]。這實(shí)際上是疑心byWest通過私人通信和證明經(jīng)過一些討論與他。2.反例的猜測.在本節(jié)中,我們給出反例猜測的Chambersetal。[2]。explosion圖的一個(gè)looplessmultigraphG是圖的頂點(diǎn)集V()=V(G)∪{,,,,:e=xy∈E(G)}和邊集E)={x,y,,,,,e:e=xy∈E(G)}參見圖1.注意那{,,,}引起一個(gè)5-cycle在,用Ce。我們叫,,為內(nèi)部頂點(diǎn)的Ce和。注意,即使G有平行邊,它的explosion圖是一個(gè)簡單的grap。定理1.有無限多的2連通圖和羅馬統(tǒng)治數(shù)至少23n/34個(gè),其中n是頂點(diǎn)的數(shù)量在grap。證明.考慮k圖,,...,,每個(gè)同構(gòu)于,和他們的explosiongraphs,,...,.讓G是2-連通圖中獲得這些explosion圖不相交的聯(lián)盟通過添加適宜的邊界的頂點(diǎn)之間的originalgraphss;i.e.這些添加的邊界和Gi’s的形成2-連通圖。然后,G存在n=34的k頂點(diǎn)。我們聲稱≥23n/34=23k。假設(shè)相反,<23k。選擇一個(gè)最優(yōu)的Roman控制數(shù)G的函數(shù)f。因?yàn)?w(f)<23k,有一些w(f)<23。注意,對于任何邊界xy在,不管什么值f(x)和f(y),它總是如此,w(f,)≥3。此外，如果f(x)≤1和f(y)≤1事實(shí)上就有w(f,)≥4假設(shè)存在r個(gè)V字形頂點(diǎn)有f(v)≤1,當(dāng)0≤r≤4。那么有()邊界xy和w(f,≥4。因此23>w(f,)≥r·0+(4?r)2+6·3+〔〕或，相當(dāng)于2r>3+〔〕，這是不可能的,因?yàn)?≤r≤4.這個(gè)下界23n/34在定理以上是存在的確實(shí)切值givengraphG.這將是看到下面的定理的證明方法,采用了一個(gè)有用的在整體論證。因?yàn)榧夹g(shù)原因,我們經(jīng)?？紤]三個(gè)Roman控制函數(shù),，我們用表示3維數(shù)組(,,),和(v)((v),(v),(v)).那么重量存在w()=,注意w()≤w()/3對一些j成立。一個(gè)頂點(diǎn)v是is-強(qiáng)連通如果(v)=2相對于一些j。定理2.如果是explosion圖的一個(gè)loopless多重圖G沒有孤立的頂點(diǎn)和有個(gè)頂點(diǎn)，然后有一個(gè)3元組數(shù)組的Roman控制函數(shù)是這樣的w()≤69/34和每一個(gè)noninner頂點(diǎn)是的強(qiáng)，此外,如果這些滿足w()=69//34,那么G是一個(gè)不相交的并集的’s。證明.如果G存在n頂點(diǎn)和m邊界,然后=n+5m，我們將首先構(gòu)建賦值0、1或2在G的頂點(diǎn)內(nèi)。為了這個(gè)目的,我們將G的階放在,,...,讓是存在于子圖G中歸納出{,...,}從而如下。注意,=G.從有i=n,做以下循環(huán):如果有一個(gè)頂點(diǎn)的度不等于3或一個(gè)頂點(diǎn)的度為3,最多只有兩個(gè)相鄰點(diǎn),然后選擇它作為;否那么選擇一個(gè)頂點(diǎn)的度3作為和它的三個(gè)相鄰點(diǎn)為,,。對于前一種情況下，讓=,然后由i代替i?1重復(fù)循環(huán);對于后一種情況，讓=和k=i,i?1,i?2,i–3，然后取代i和i–4重復(fù)循環(huán)。每邊的G作為“下降邊界”的一些2和i>k。因此有m=。一次()被定義為k<i這樣()=2一些我們定義()和()=2一些根據(jù)以下情況下。如果有(x)≤1和(y)≤1我們叫xy邊界為G的一個(gè)1型邊界存在于。否那么它是2型邊界。在下面,我們將計(jì)算每邊的G三次作為一個(gè)1型或2型邊界存在3種s。案例1.≥4.在這個(gè)案例中，我們讓()=(2,2,2)。然后,對一些s而言有所有的是算作1型邊界。同時(shí),存在有=1。案例2.≤2或=3，但最多只有兩個(gè)相鄰數(shù)。在這種情況下，有一些,存在下降邊界對于任何和成立.。當(dāng)j時(shí)定義()=2和()=0。案例3.=3對于i≤≤i+3，在是一個(gè)下降邊界i≤≤i+2。在這種情況下，對于≤2有i≤≤i+2和=3.有i≤≤i+3，類似案例2,我們可以選擇一些。對于至少的存在的數(shù)組{2,}有下降邊界與。定義()=2和()=0對于所有的有j.有，作為1型邊界一些s，假設(shè)存在i≤≤i+2和i’=i+3對于大多的次數(shù)與一些不超過4=1+的次數(shù)，有,+1,+2,vi+3,是的下降邊界當(dāng)做1型邊界對一些頂多存在1+次,這里≥6。現(xiàn)在,我們已經(jīng)指定(v)的值,這樣v是強(qiáng)對于所有的頂點(diǎn)v是屬于G。然后我們分配值在所有個(gè)頂點(diǎn)上,這里有e=xy,所以有因?yàn)镚沒有孤立的頂點(diǎn),,和所以是Roman控制數(shù)函數(shù),對于1型邊界xy有一些是屬于G的，存在()=()=2就有2型邊界xy有一些是屬于G。因此有，所以(x)=(y)=2，我們就得到()=()=2其中和是的強(qiáng)。接下來,我們計(jì)算w()，假設(shè)有c是指數(shù)為i簡單函數(shù),3的格林關(guān)系是Gi，列如案例3，然后4c≤nand6c≤:案例3}≤m因?yàn)榇嬖?c≤n+5m=n’andsoc≤n’/34因此,我們有此外,當(dāng)w()=69n’/34c必須等于n'/34,因此6c=:屬于案例3}=m這意味著例1和2從未發(fā)生過。有序算法{,,...,}在開頭提到的證明,G必須是一個(gè)不相交的并集的’s。這就完成了定理的證明。3.2-連通圖的Roman控制數(shù)。在本節(jié)中,我們建立我們的主要結(jié)果為2-連通圖的Roman控制數(shù)定理3.對于任何2-連通圖G的n個(gè)頂點(diǎn)存在≤max{[2n/3],23n/34}.此外，如果23n/34>[2n/3]和G是一個(gè)不包含子圖同構(gòu)的explosion圖有一個(gè)不相交的并集K4’s,有<23n/34。證明。假設(shè)相反,定理是錯(cuò)誤的和G是一個(gè)最小的反例的定理。換句話說,G是2-連通圖的n階>max{[2n/3],23n/34}和任何2-連通圖與有序數(shù)組存在+|E()|<n+|E(G)|滿足γR()≤max{[2n/3],23/34}，特別是,G是一個(gè)最小2-連通圖。根據(jù)引理4,我們有以下要求。要求1。G沒有周期和和弦。引理4(Dirac[6],Plummer[12])。一個(gè)2-連接圖是最小2-連接圖當(dāng)且僅當(dāng)每一個(gè)循環(huán)是一個(gè)歸納的周期。證明。假設(shè)相反,G有兩個(gè)不完整的5-cycle和,頂點(diǎn)不相交。有=其中,是兩個(gè)頂點(diǎn)的至少為3的度其中i=1,2,假設(shè)有=側(cè)=?，F(xiàn)在我們考慮圖中獲得的歸納子圖G滿足V(G)?{:i=1,2,j=2,4,5}通過添加邊和.很明顯,有種2-連通圖頂點(diǎn)滿足=n?6和的極小性的G滿足|E()|<|E(G)。我們有γR()≤max{[2/3],23/34}.選擇一個(gè)Roman控制數(shù)函數(shù)和滿足w()=γR()，定義函數(shù)g和V(G)滿足g(v)=(v)所以有v∈v(C1∪C2)和當(dāng)i=1,2.然后g是一個(gè)Roman函數(shù)G的控制數(shù)滿足w(g)≤w()+4.假設(shè)γR()≤max{[2n/3],23n/34}成立,側(cè)存在一個(gè)不一致的控制數(shù)G。注意,每個(gè)不完整的5-cycle函數(shù)在G上可以擴(kuò)展到一個(gè)explosion圖,但是它們在一起不一定是explosion圖。作為一個(gè)頂點(diǎn)村在一些不完整的5-cycle函數(shù)可能是explosion圖的頂點(diǎn)的K2，這是來自另一個(gè)不完整的5-cycle延長。然而,下面的引理將產(chǎn)生explosion圖重疊的所有不完整的5-cycle函數(shù)在通過G選擇S為空集。引理5。我們給定一個(gè)圖中,H中任何兩個(gè)不完整的5-cycle函數(shù)的頂點(diǎn)不相交,讓S有一個(gè)子集的V(H)。如果每一個(gè)不完整的5-cycle函數(shù)至少有兩個(gè)相鄰的頂點(diǎn)C和H其中滿足H?V(C)。存在H有子圖同構(gòu)explosion圖且L的一個(gè)loopless多重圖沒有孤立的頂點(diǎn),這樣沒有不完整的5-cycles函數(shù)在H是頂點(diǎn)別離從S∪V(L),但是每一個(gè)不完整的5-cycle函數(shù)L是頂點(diǎn)不相交的S函數(shù)。證明。假設(shè)H存在不完整5-cycle函數(shù)k有,,...,所以S是vertexdisjoint函數(shù)。當(dāng)和是至少存在兩個(gè)度為3的頂點(diǎn)i，我們將證明引理歸納在k中，這個(gè)引理明確指出k=0?，F(xiàn)在假設(shè)k≥1.構(gòu)造一個(gè)輔助有向圖F滿足V(F)={}和E(F)={∈E(H):在H上的度為3}然而每個(gè)的引入度都有≤1和=1出度為≤1.因此,至少有一個(gè)指數(shù)r有≤1和≤1.否那么,對于每一個(gè)i有≥2或≥2成立同樣有=0或deg?Dvi,3=0成立。前者意味著|E(F)|=≥2k，而后者意味著|E(F)|=≤k<2k,從而不一致。當(dāng)j=1,3,因?yàn)橹辽儆袃蓚€(gè)頂點(diǎn)滿足H?V()于x相鄰，我們可以選擇一對鄰居與滿足V(H)\V()這樣都有=，從而加上和的邊界是一個(gè)explosion圖其邊界是。讓是圖H通過刪除所有得到的邊界的函數(shù)，有存在S∪{}。從而是V()的一個(gè)子集，每一個(gè)不完整的5-cycle函數(shù)的頂點(diǎn)是不相交的。H必須是一個(gè)不完整的5-cy