【doc】有向笛卡尔积图的有向度量维数

【doc】有向笛卡尔积图的有向度量维数 有向笛卡尔积图的有向度量维数 第45卷第1期 2012年3月 数学研究 JournalofMathematicalStudy v()J_45NO.1 Mar.2012 TheDirectedMetricDimensionofCartesian ProductofDigraphs BaiYanruHuangXiaohuiZhangZhao (CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang830046) AbstractForave~exsetW={11,t,72,...,)ofadigraphDandavertex?(D), the(directeddistance)representationofwithrespecttoWistheorderedk-tuplerf,IW1: (d(v,w1),e(v,w2),…,d(u,叫k)),andWisaresolvingsetofDiflr(uI)?r(~lW)holdsforany pairofdistinctverticest'andu.TiledirectedmetricdimensionofD,denotedbydim(D),isthe cm-dinalityofasmallestresolvingsetofD. Inthispaper,westudythedirectedmetricdimensionoftheCartesianproductdigraphD1xD2. LetPmandbethedirectedpathandthedirectedcycleoflengthm,respectively.Alower boundisgivenfordim(D1XD2),andupperboundsaregivenfordim(D× 只)anddim(DXCm), respectively.Theexactvaluesofdim(P,~×P4,dim(Cm×,),anddim(C× C)aredetermined, whichshowsthatourupperboundsaresharp. KeywordsDirectedmetricdimension;Cartesianproduct;Resolvingset CLCnumberO157.5DocumentCOdeA 1Introduction Theconceptofmetricdimensionof(undirected)graphswasintroducedbySlater[1,21. Applicationsofthisparametertothenavigationofrobotsinnetworks[a]andchemistry[41 werediscussed.Chartrandeta1.generalizedthisconcepttodigraphs[5]. LetD=((D),(D))beadigraph,whereV(D)andA(D)arethevertexset andthearcsetofD,respectively. Itisstronglyconnectedifforanytwovertices U,W?(D),thereisadirectedWpathinD.Itisconnectediftheunderlying undirectedg1'aphofDisconnected.Inthispaper, adigI?aphisalwaysassumedto Receiveddate;2011-11—27 Foundationitem;TheprojectwassupportedbyNSFCflO97】255)andTheProject— sponsoredbySRF forROCS,SEM. 9数学研亢2012龟 beconnected.butstrongconnectednessisnotrequired? F0rtwovertices.?V(D),weusedn(u,tu)todenotethedistancefromuto _fjjinD.i.e..thelengthofashortestdirectedcl7_』』pathinD.Asconvention:ifthere isnodirected'u-~l/pathinD,thendD(,,'UJ)=?.WhenthedigraphDisclearin thecontext,thesllbscriptDisomitted.LetW='U71,ll32….,训}V(D)bean orderedvertexsubset.Foravertex?V(D),the一tuple ' (训)=((2),(2(,w2),…,a(v,叫)) iscaliedtherepresentationofwithrespecttoW.TilevertexsubsetWisa resolvingsetofDiftherepresentationsofanytwovei'ticesofv(o)withrespect toare出fferent.Noticethat伽istheonlyvertexofV(D)forwhichtheith co一0rdiIlate0fitsI?epresentationis0.Therefore,tocheckwhetherWisaresolving setforDoneonlyneedstocheckwhethertherepresentationsforanytwoverticesof V(D,一Waredifferent.Aresolvingsetoftheminimumcardinalityiscalledabasis fbrDanditscardinairyisthedirectedmetricdimensionofD,denotedbydim(D). ForabasisW=l,l!c,2,…,,wk},ifd(v,UTi)<..holdsforanyvertex"?V(D) andanyi?{l,2...,,thenwecallWasagoodbasisofD.Noticethatour deftI1itionisdifferentfromthatinf51inwhichitisrequiredthat(f(u,1』J)<o.holds forevervvertexandeveryi,andthusaI1existenceproblemhastobestudiedfirst? underourdefinition,dim(D)existsforanydigraphD,butDdoesnotnecessai'ily hayeagoodbasis.Forsimplicityofstatement:ifd(u训)?d(v,w)forsomevertex 1L,?W.thenwesaythat1uandareresolredbyw. In,Chartrandeta1.chai?acterizedthoseorientedgraphshavingmetricdi一 ?1ension1.Tl1eyalsoshowedthatinaconnectedorientedgraphDwithorder 7twhjchhasagoodbasis,iftheout—degreeofeveryVeI'texisatleast2,then diII1f1<7一3andthisboundissharp.Propertiesofmetricdimensionlnorlented raDhswerefurtherstudied[.1. Fehreta1.gavesharpupperandlowerboundsfor themetri(:diInensionoftheCayleydigraphsCay(a:r),whereI1isthegroup 0.,0…?f)andA={(1,0,0,…,O),(0,1,0,0….,O),…,(0,0,…,【),1).} isthecanonicalsetofgeneratorsforr【71. Inparticular,theexactvalueforthe n1etricdimensi0nof(f(0,1),(1,0)):?)isderived.Themetricdimension oftheCaytevdigraphonthedihedralgrinlpDnoforder2'nwithaminimunlsetof encrat0rsisobtained[7.. ThemetricdimensionofC,ayleydigraphsofabeliangrinlps 第1期BaiYanrueta1.:TheDirectedMetricDimensionofCartesianProduct3 werestudiedIsj. Forthenletricdimensionofundirectedgraphs,Brighameta1.investigatedthe relationshipamongmetricdimension,dominationnumberandresolvingdomination number[.1.Khullereta1.showedthatthemetricdimensionofagraphwithnnodes CallbeapproximatedinpolynomialtimewithinafactorofO(1og几1-3J. TheCartesianproductoftwodigraphsD1andD2isthedigraphD=D1×D2 whose,vertexsetis(D1×D2):={(1,V2):?V(Di),i=1,2},and("1,2) isadjacentto(Wl,W2)(i.e.,thereisanarcfrom(Vl,732)to(*U1,2))ifandonlyif either731=WlandV2isadjacenttoW2inD2,orv2:2and1isadjacenttoW1in D1.Bythisdefinition,itiseasytoseethatforanytwovertices(Vl?"02)and(W2) inD:D】×D2, D((1,u2),=dD1(Vl,W1)+dD2(V2,(1) Asaconsequence,DIXD2isstronglyconnectedifandonlyifbothD1andD2are stronglyconnected. ForCartesianproductundirectedgraphs,Cacereseta1.studiedboundsfor theirmetricdimensionanddeterminedtheexactvaluesforsomespecialCartesian productgraphs[】. Furthermore,theyconstructedafamilyof(highlyconnected) graphswithboundedmetricdimensionforwhichthemetricdimensionoftheCarte— Manproductisunbounded.Chartrandshowedthatdim(H)dim(H×K2) dim(H)+1holdsforeveryconnectedgraphH,andforeverypositiverealnumber ,,thereexistsaconnectedgraphGandaconnectedinducedsubgraphHofGsuch thatdim(G)/dim(H1<,【4J. Someotherrelatedstudiescanbefoundin15]. Asfara8weknow,thereisnoworkonthedirectedmetricdimensionforthe Cartesianproductdigraphs.Let7孔beapositiveinteger. Weuse),nandC todenotethedirectedpathandthedirectedcycleoflength竹,respectively(i.e., thenumberofarcsonorC『mis").Inthispaper,wegivealowerbound fordim(D1×D2),andprovideupperboundsfordim(D×)anddim(D×). Then,weshowthattheupperboundsaresharpbydeterminingthedirectedmetric dimensionof×,×and× 4数学研究2012午 2Boundsfordim(D×)anddim(D×) "layeringstructure"ofCartesianproductD=Dl×D2.Fm.afixedvertex U0?(D1),thesub—digraphofDinducedbythevertexset(v0:/)2)lU2?V(D2)), denotedasDisisomorphictoD2.WecallitaD2一copy.TileconceptofDl—copy Callbedefinedsimilarly.PuttingtheverticesofDinacoordinatesystem,itcanbe seenthatDcanbedecomposedinto"horizontallayers"ofDt—copiesrviewthem asrOWS)and"verticallayers"ofD2一copies(viewthemascolumns). ForavertexsubsetWofD=D1×D2,theprojectionsofWontoD1and D2arethevertexsetsProj1(W)={1lthereexistsavertex(VlU2)?)and Proj2()={2Ithereexistsavertex(Vl,V2)?},respectively. Theorem1dim(D1×D2)max{dim(D1),dim(D2)}. ProofLetWbeabasisforD:DI×D2.Fixanai'bitraryvertex2,2?V(D2). Forartytwovel'tices,721?V(Dt),sincer((U2)IW)?I厂((1,V2)I),there existsavertex(IL,'I,'1122)?WsuchthatdD((Vl,u2),(7131,w2))?D((l,u2),(W1,w2)). CornbiningthiswithdD1(U1,W1)+dD2729,叫2)?dD1("U1,叫1)十dn2(2,2),andthus cfDl(Ui,[U1)?dDl(1,w1).Noticethat'W1?Proj1().Bythearbitrarinessofu1 andl,WOseethatProjl(W)isaresolvingsetofDt,andthusdim(Dr×D2)= fWj2}Proj1()}dim(D1).Similarly,dim(Dr×2)dim(D2). Next,"v\restudytileupperboundfordim(D×)anddim(D×n). Theorem2ForanyconnecteddigraphDwhichhasagoodbasis. dim(D×)rain{IDl,dim(D)+7n) ProofSupposedim(D)=t.LetV(D)={,l,2,…,),=~/,12/,2...?zu.,,+l, andWbeagoodbasisofD.Assume,withoutlossofgenerality:thatW= U'2…,}.Weconsiderthefollowingtwocases. Casel}Dldim(D)+m. Inthiscase,weshallshowthatthevertexset S={(72,,7/,i),(,,7/,2),(),(721,U,rn+1),("U2,7Zm+1)….,(,%trn+1)} isaresolvingsetofD× Let(72i.t))betwodistinctverticesinV(D×) 塑塑.望!!型:!!!!ctedMetricDimer1sjonofCartesianProduct————'——————— ———————_—————'————————————————————— ——————————————………uu…1 nthecasethatP:==q, wehavet?.SinceW={l,2…)isabasis ofD,thereexistsavertext?WsuchthatdD(,)?dD(u,). CombiI1ing thiswith(1),wehavedD×Pm((?几,up),(Vk,7Lm+1))=ds(vk)+dpm(1zp,m+1)? dD(,u)+(z只,(扎q,71,rn+I.)=dn×((,'z口),(Uk,m+1)).So,(?,.,up)andVj7. tq)are resolvedby屉,?ff'm+1). IntheCaSethatP?q,suppose,withoutlossofgeneralitythatp<口.Because isagoodbasisof.D,wehavedD(,)<..andthusdDxP,,,((,),(,)): D,)<.C,Ontheotherhand,sinced(口,):o.,wehavedD~((,口), (t,札p)):==cx.?So,(13i,u)and(,u叮)areresolvedby(2,up). BYthearbitrarinessof(,t)and(Vj,g),weseethatSisaresolvingsetof D×,andthusdim(D×Pm)ISl=diln(D)+m. Case2IDIdim(D)+m. Inthiscase,weshallshowthatthevertexsetS= {(~Zm+1),(u2,l"m+1), …, (Vn,~Zm+I)isaresolvingsetofD×. LetYi,uv),(,札q)betwodistinctverticesinV(D×)m). Intt1ecasethat .=:=wehave?q,andthusdD×((,),(,m+1))一dPm(~p,一u刑一1)? d尸m(ug,u"+1j:==dDx((,,"q),(,钆m+1)).Inthecasethati?,,vehavedD(uj,) >0?S1】pp0se,wihoulossofgenerality ,thatP三三=口.ThendDxP,,~((,up),(,札+1)) dPlm(u|p,n+1)二三三Pm(q,"n+1)<dD(vj,)+dPm(~q,%tin+I)=dDxP,.((,口), 札m+1))_InanYcase,(,札p)and(0,乱g)areresolvedby(,+1).Bythe arbitrarinessof(t以,p)and(vj,ug),SisaresolvingsetofD×)m,andthus dim(D×)}Sj=jD}_ Theorem3ForanyconnecteddigraphD , dm(D×(/rm)?min{IDi,dim(D)+m一1}. ProofTheproofjssimilartothatofTheorem2 .Weonlyfocusonthedif- ferencesnthefollowing- UsethesalllenotationasinTheoI.em2exceDtthat (=u12…u?n钆1. hthecasehatlDI三三=dim(D)+仃—l,itcalnbeshowntha,thevertexset === {(仇1),(,?2)…?,";),(l,urn),('U2,m)….,(_l】饥)}isareSolvingset ofD×Gn—TheprO0fdiffersfromthatofTheorem2wl1enp?g. sup.se and)cannotberesolvedby(,uv),j.e_,×((,Up),(,"p)): dD×c mq)"p))?Tl1ellweseefrom(1)that()=dD(vj,仇)+矗(,) 6数学研究2012侄 Noticethatdc(,"q札p)+dc(札p,uq)=m>0.HencedD×e((t_"p),(u,uq)): dD dD vi,)+dc(up札q)=dD(Vj,t)+dc(r"q,"l,)+dco,(u_p,口)=矗D(,)+,,> ,",)=du×((,Uq)(钉,,扎9)).So,(vi,p)and(,Uq)areresolvedby(,,?zq). InthecaseIDldim(D)+m一1,byasimilarargumentasinTheorem2,itCaD beshownthatS={(1)1,U.rr,),(2,u)...,(,"Lt.rn))isaresolvingsetofD×(. Theorem4dim(P.×)=min{m,7)+1 proofLet,=Ul~Z2....m+1,='U1'U2…Ur.+1.Noticethatthedirected metricdimensionofanydirectedpathis1,withtheheadofthedirectedpathbeing thebasis. ByTheorem2,wehavedim(Pm×Pn)nlin{tI,dim(Pm)+佗)=min{m+ l,n+1}.Weshallderiveacontradictionifthestrictinequalityholds. LetWbeabasisof×.Supposedim(×)<min{m+1,7+1 thenthereexistsanindexE{l,2,...,m+1)suchthat()nw=, andthereexistsaI1indexfE{12,...,7+1}suchthatWnf)=.If =m+1,thenbranyindexiE{l,2.,_几+1'},therepresentationofvertex (u7n+l,'vi)withrespecttoWis(?,,..,0.),andthusverticesinm十lcannot beresolved.Therefore:<7n+1.Similarly,f<『n+1.Next,weshowthat ,((u,va+~)tW)=r((+l,f){).Let(i,)beavertexinW.Noticethati?七 since(uk))nW=andj?fsinceWn()=.Ifk<<7n+1 and?<. 佗+1,then×只((,Ul+1),(tti,t0))一dpm(irk,Ui)+(f(Uf+1,U)= dp.(1tk+l'Iti)+1+d(,)一1=dPm×(1tk+1,v1),(,)).Ifi<korJ<l,then either(札,1/,i)=o(3orda(,cJf,Cj)=,CX5,andthus矗只,x((札^:,Vl+1),(钆,t0))= d×R(Uk+l,v1),(Hi,))=oo.Hence(,'Ul+1)and(u+l,)cannotberesolved bv,acontradiction. Theorem5dim(×)=min{m,凡+1} proofLet』[=='tL1lt,2…U,nlZn+1C,n=Vlu2...Vr~z'U1aridWbeabasisof× m. ByTheo~'eel3,wehavedim(P,×)min{Ij,dim()+r,.一1)= min{n+1;?).Supposedim(×)<inin{n+1,_r,},thenthereexistsanin— dex^:E{1,2,...,n+1}suchthat(C)nW=andthereexistsanil】dex f?{1;2,…)suchthatWn("?)=().SimilarlytotheargumentofTheorem 4,wehave后<凡+1.Furthm'more,iff=m,werega~'d?+1=1.Next,weshowthat 7'((?z,Ul+1)lW)=7'((u+l,')lW).hafact,foranyvertex(,"j)?W,ifk<in+ 第1期BaiYanrueta1.:TheDirectedMetricDimensionofCartesianProduct, 1,thend×G((,",f+1),(u,"Uj))=dp,~(uk,Ui)+dc(Vl+l,Uj)=(f(Uk+l,/Zi)+1+ de.(uf,)一1=dR.×((u+1,f),(u,J))(noticethatdc,,(Vl+lVj)=de(zj)一 1holdsbecauseJ?1).Ifi<,thendR.(^:,I1,i)=dR,(饥+1,tti)=o.,andthus f2只×cm((u,l"l+1),("i,J3))=×e((十1,,f),(",))=o..Hence,acontradic— tionisobtainedsince(札,,f+1)and("十1,'U1)cannotberesolvedbyW. Theorem6dim(×):min{m,n} proofNoticethatthedirectedmetricdimensionofany withanyonevertexofthedirectedcyclebeingabasis.Then provedbyasimilarargumentastheabove,usingTheorem3. directedcycleis1, thetheoremcanbe Theorem4,Theorem5andTheorem6showsthesharpnessoftheupperbounds inTheorem2andTheorem3. References SlaterP.J..Leavesoftrees.Proc.6thSoutheasternInt.Conf.onCombinatorics, GraphTheoremandComputing,inCongr,14(1975):549—559 [2】SlaterP…JDominatingandreferencesetsingraphs.J.Math.Phys.Sci.,22(1988) 445—455. 【3】KhullerS.,RaghavachariB.,RosenfeldA..Landmaksingraphs.DiscreteApplied Mathematics,70(1996):217—229. ChartrandG.,ErohL.,JhonsonM.A.,OellermannO.R..Resolvabiblityingraphs andthemetricdimensionofagraph.DiscretAppliedMathematics,105(2000):99—113. ChartrandG.,12ainesM.,ZhangP.,Kalamazoo.Thedirecteddistancedimensionof orientedgraphs.MathematicaBohemica,125(2000):155—168. [6]ChartrandG.,RainesM.,ZhangP..Onthedimensionoforientedgraphs.Utilitas Math.,60(2001):139—151. FehrM.,GosselinS.,OellermannO.R..ThemetricdimensionofCayleydigraphs DiscreteMathematics,306(2006):31—41. [8】OellermannO.RPawluckC.,StokkeA..ThemetricdimensionofCayleydigraphs ofabeliangroups.ArsCombin.,81(2006)"97—112. [9]BrighamR.C.,Orlando,Charti'andG.,Kalamazoo,DuttonR.D.,ZhangP.,Resolving dominationingraphs,MathematicaBohemica,128(1)(2003):25—36. [10]CaceresJ.,HernandoC.,MoraM.,PelayoI.M.,PuertmsM.L.,SearaC..Onthe 8数学研究2012年 nietricdimensionof matics,21(2)(2oo7) Cartesianproductofgraphs.SIAMJournalofDiscreteMathe. 273—302. [11]CaceresJ.,HernandoC.,MoraM.,PelayoI.M.armPuet?tasM.L..Onthemett?icdi— rnensionofinfinitegraphs.ElectronicNotesinDiscreteMattmmatics,35(2009):15—20. [12]CaceresJ.,HemandoC.,MoraM.,PelayoI.M.,PuertasM.L.,Seat-aC..OntherI1etric dimensionofsomefamiliesofgraphs.ElectronicNoteinDiscreteMathematics , 22 (2005):129—133. [13]HararyF,andMelterR..Onthemetricdimensionofagraph.ArsCombinatoria2 (1976):191—195. [14]OellermannO.R.,FransenJ.P—Thestrongmetricdimensionofgraphsanddigraphs. DiscreteAppliedMathematicsj155(2007):356—364. [15]OellermannO.R.,Peters—FransenJ— MetricdimensionofCartesianproductsofgraphs. UtilitasMath,69(2006):35,一41. 有向笛卡尔积图的有向度量维数 白燕茹黄晓晖张昭 (新疆大学数学与系统科学学院,新疆乌鲁术齐830046) 摘要设J[)是一个有向图,W={,uJ1,?2,.…W}是D的一个有序点子集,足D 中任意一点.我们把有序元素组r({)=(d(v,1),d(v,w2),…,d(,Wk))称为点U对 于的(有向距离)示.如果在D中,任意两个不同的点r"和对的(有向距离) 表示都不相同,则称是有向图D的一个分解集.我们把D的最小分解集的基数称为 有向图D的有向度量维数,并用dim(D)来表示. 本文研宄了有向笛卡尔积图D1XD2的有向度量维数.设Pm和分别是长为 的柯向路和有向圈.在文中我们分别给出了dim(Di×D2)的一个下界与dim(D×.) 和dim(DXc)的卜界,并通过确定dim(×),dim(CX.)和dim(cX)的 精确值说明了我们给出的界是紧的. 关键词有向度量维数;笛卡尔积;分解集