A characterization of 2-dimensional Cayley graphs on dihedral groups 7 1 0 A.Behtoei1 2 DepartmentofMathematics,ImamKhomeiniInternationalUniversity, n P.O.Box:34149-16818,Qazvin,Iran,[email protected] a J 9 Y.GolkhandyPour 2 DepartmentofMathematics,ImamKhomeiniInternationalUniversity, P.O.Box: 34149-16818,Qazvin,Iran,[email protected] ] O C . h t a m Abstract [ AsubsetW oftheverticesofGisaresolvingsetforGwhenforeachpairofdistinctvertices 1 u,v∈V(G) there exists w∈W such that d(u,w)6=d(v,w), where d(x,y) denotes thedistance v between two verticesx and y. The cardinality of a minimum resolving set for G is themetric 4 dimensionofG. Thisconceptariseinmanydiverseareasincludingnetworkdiscoveryandveri- 8 fication,robotnavigation,problemsofpatternrecognitionandimageprocessing,coinweighing 3 problems,strategiesfortheMastermindgame,combinatorialsearchandoptimization.Theprob- 8 lemoffindingmetricdimensionisNP-completeforgeneralgraphs.Inthispaper,wecharacterize 0 allofCayleygraphsondihedralgroupswithmetricdimensionistwo. . 1 0 Keywords:Metricdimension,Cayleygraph,Dihedralgroup. 7 1 MSC(2010):Primary:05C25,05C75,20B10. : v i X 1 Introduction r a Let G =(V,E) be a simple and connected graph with vertex setV and edge set E. The distance betweentwoverticesx,y∈V isthelengthofashortestpathbetweenthemandisdenotedbyd(x,y). If d(x,y)=1, then for convenientwe write x∼y. The neighborhoodof x is N(x)={y: x∼y}. ForanorderedsubsetW ={w ,w ,...,w }ofverticesandavertexv∈V,thek-vectorr(v|W):= 1 2 k (d(v,w ),d(v,w ),...,d(v,w ))iscalledthemetricrepresentationofvwithrespecttoW. ThesetW 1 2 k iscalledaresolvingsetforG ifdistinctverticesofG havedistinctrepresentationswithrespecttoW. Eachminimumresolvingset isa basisandthe metric dimensionofG , dim (G ), isthe cardinality M of a basis for G . This concept has applications in many areas including network discovery and verification[2], robotnavigation[11], problemsof patternrecognitionandimageprocessing[12], coin weighing problems [15], strategies for the Mastermind game [5], combinatorial search and optimization [15]. These concepts were introducedby Slater in 1975 when he was working with 1Correspondingauthor 1 U.S.SonarandCoastGuardLoranstationsandhedescribedtheusefulnessoftheseconcepts,[16]. Independently,Harary and Melter [9] discovered these concepts. Finding families of graphswith constantmetricdimensionorcharacterizingn-vertexgraphswith a specifiedmetricdimensionare fascinatingproblemsandatractsthe attentionofmanyresearchers. Theproblemof findingmetric dimensionisNP-Completeforgeneralgraphsbutthemetricdimensionoftreescanbeobtainedusing apolynomialtimealgorithm.In[13]themetricdimensionfortwodifferentmodelsofrandomforests isinvestigated. Itis nothardto see thatforeach n-vertexgraphG we have1≤dim (G )≤n−1. M Chartrandetal.[6]provedthatforn≥2,dim (G )=n−1ifandonlyifG isthecompletegraphK . M n Themetricdimensionofeachcompletet-partitegraphwithnverticesisn−t. Theyalsoprovided acharacterizationofgraphsofordernwithmetricdimensionn−2,see[6]. Graphsofordernwith metricdimensionn−3arecharacterizedin[10]. Khulleretal.[11]andChartrandetal.[6]proved thatdim (G )=1ifandonlyifG isapathP . Themetricdimensionofthepowergraphofacyclic M n group is determined in [8]. Salman et al. studied this parameter for the Cayley graphs on cyclic groups [14]. Each cycle graphC is a 2-dimensional graph (dim (C )=2). All of 2-trees with n M n metricdimensiontwoarecharacterizedin[3]and2-dimensionalCayleygraphsonAbeliangroups arecharacterizedin[18]. Moreover,in[17]somepropertiesof2-dimensionalgraphsareobtained asbelow. Theorem1.1. [17]LetG bea2-dimensionalgraph.If{u,v}isabasisforG ,then 1. thereisauniqueshortestpathPbetweenuandv, 2. thedegreesofuandvareatmostthree, 3. thedegreeofeachinternalvertexonPisatmostfive. The Mo¨bius Ladder graph M is a cubic circulant graph with an even number n of vertices n formedfromann-cyclebyconnectingoppositepairsofverticesinthecycle. Forthemetricdimen- sionofMo¨biusLadderswehavethefollowingresult. Theorem1.1. [1]Letn≥8beanevennumber. ThemetricdimensionofeachMobiusLadderM n is3or4. Specially,dim (M )=3whenn≡2(mod8). M n Ca´cereset al.studiedthemetricdimensionoftheCartesianproductofgraphs. Theorem1.2. [4]LetP beapathonm≥2verticesandC beacycleonn≥3vertices. Thenthe m n metricdimensionofeachprismP ×C isgivenby m n 2 n odd, dim (P ×C )= M m n (3 n even. Let G be a group and let S be a subset of G that is closed under taking inverse and does not containtheidentityelement,saye. RecallthattheCayleygraphCay(G,S)isagraphwhosevertex setisGandtwoverticesuandvareadjacentinitwhenuv−1∈S.SinceSisinverse-closed(S=S−1) and does not contain the identity,Cay(G,S) is a simple graph. It is well known thatCay(G,S) is a connected graph if and only if S is a generating set for G. In this paper, we study the metric dimensionofCayleygraphsondihedralgroupsandwecharacterizeallofCayleygraphsondihedral groupswhosemetricdimensionistwo. 2 2 Main results Atfirst, weprovidetwousefullemmasondihedralgroupsanda sharplowerboundforthemetric dimensionof3-regularbipartitegraphswhichwillbeusedinthesequel. Lemma 2.1. The subset {aib,ajb} is a generating set for dihedralgroup D =ha,b| an =b2 = 2n (ab)2=eiifandonlyifgcd(n,i−j)=1. Proof. Itisstrightforwardusingthefollowingfactaboutthesubgroupgeneratedbytheseelements. haib,ajbi={a(i−j)t, a(i−j)t+ib, a(i−j)t+jb|t∈Z}. Lemma2.2. If4|nandgcd(i−j,n)=2,then{a2n,aib,ajb}isnotageneratingsetforD2n. Proof. Sincehai−jiandha2iaretwocyclicsubgroupsoforder n inthecyclicgrouphai, wehave 2 ha2i=hai−ji⊆h{an2,aib,ajb}i. Since4|n,an2 ∈ha2iandhence,h{a2n,aib,ajb}i=h{aib,ajb}i. NowtheresultfollowsfromLemma2.1. Lemma2.3. LetG bea3-regularbipartitegraphonnvertices. Thendim (G )≥3. M Proof. SinceG isnotapath,dim (G )isatleasttwo. Supposethatdim (G )=2andletW ={u,v} M M be a resolving set for G . Assume that d(u,v)=d and N(u)={u ,u ,u }. It is easy to see that 1 2 3 d(u,v)∈{d−1,d,d+1},foreach1≤i≤3.Ifthereexist1≤i< j≤3suchthatd(u,v)=d(u ,v), i i j thenr(u|W)=r(u |W),whichisacontradiction.Hence,withoutlossofgenerality,wecanassume i j that d(u ,v)=d−1, d(u ,v)=d, d(u ,v)=d+1. 1 2 3 Let s be a (shortest) path between two vertices u and v of lengh d, and s be a (shortest) path 1 2 betweentwoverticesu andv. Twopathss ands usingtheedgeuu produceanoldclosedwalk 2 1 2 2 oflengh2d+1inG whichcontradictsthefactthatG isabipartitegraph. Forthesharpnessofthis bound,considerthehypercubeQ =K ×K ×K . 3 2 2 2 InTheorem2.4wecharacterizeallofCayleygraphsondihedralgroupswhosemetricdimension n istwo. RecallthatthecenterofD2nisha2iwhenniseven,otherwiseitisthetrivialsubgroup{e}. Theorem2.4. LetSbeageneratingsubsetofD =ha,b|an=b2=(ab)2=eisuchthate∈/S= 2n S−1. Thenwehavedim (Cay(D ,S))=2ifandonlyifoneofthefollowingsituationsoccures. M 2n a) n=|S|=2, b) S={aib,ajb}andgcd(i−j,n)=1, c) nisoddandS={ai,a−i,ajb}withgcd(i,n)=1and j∈{1,2,...,n}. Proof. SinceD isnotacyclicgroup,wehave|S|≥2. Assumethat|S|=2andS={x,y}. Since 2n S=S−1andD2nisnotcyclic,wehavey6=x−1andx2=y2=e. IfS={a2n,ajb}forsome1≤ j≤n, thentheconditionD =hSiimpliesthatn=2andD =D . Otherwise,S={aib,ajb}andusing 2n 2n 4 Lemma2.1wehavegcd(i−j,n)=1. Hence,Cay(D ,S)isaconnected2-regulargraph(acycle) 2n anddim (Cay(D ,S))=2. If |S|≥4, thenthe degreeof eachvertexinCay(D ,S)is at least4 M 2n 2n andpart(2)ofTheorem1.1impliesthatdim (Cay(D ,S))≥3. Nowassumethat|S|=3. SinceS M 2n isageneratingsetande∈/S=S−1,weconsiderthefollowingcases. 3 Case1. S={ai,a−i,ajb}. Since(ajb)(ai)t(ajb)=a−it,theorderofaiis n andSisageneratingset,wehavegcd(i,n)=1. gcd(i,n) ThusO(ai)=nandverticesani,a(n−1)i,...,a2i,aiinduceann-cycleinCay(D ,S). Sinceaj∈haii, 2n thereexistsk∈{1,2,...,n}suchthataj=aki. Thereforenvertices akib,a(k+1)ib,...,a(k+n−2)ib,a(k+n−1)ib induceanothercycleinCay(D ,S). Nowforeach1≤ℓ≤nletM ={aℓi,a(k+n−ℓ)ib}. Notethat 2n ℓ ani=eandM ∩M =0/ foreachs6=k.Sinceaℓi(a(k+n−ℓ)ib)−1=akib=ajb∈S,twoverticesaℓiand s k a(k+n−ℓ)ibareadjacentinCay(D ,S). Thus,theedgesM ,M ,...,M provideaperfectmatchingin 2n 1 2 n Cay(D ,S). Consequently,Cay(D ,S) is isomorphicto P ×C . Now Theorem1.2 implies that 2n 2n 2 n dim (Cay(D ,S))=2ifandonlyifnisodd. M 2n Case2. S={an/2,aib,ajb}wherenisanevennumber. Let x =aib and y= ajb. Since an/2 is in the center of D2n and O(an2)=2, hSi=haib,ajbi∪ an/2haib,ajbi. Thus,a∈haib,ajbiora∈an/2haib,ajbi. Notethat|han/2,aibi|=|han/2,ajbi|=4. Thus,a∈/han/2,aibianda∈/han/2,ajbi. Subcase2.1. a∈haib,ajbi. Inthiscase,usingLemma2.1wehavegcd(i−j,n)=1.Thus,O(xy)=O(ai−j)=nandCay(D ,S) 2n containsaHamiltoniancycle(on2nvertices)asbelow. e∼y∼xy∼yxy∼(xy)2∼y(xy)2∼...∼y(xy)n−1∼(xy)n=e. ForeachdivisordofnthecyclicgroupZ hasuniquecyclicsubgroupoforderd.Sincehai−ji=hai n and|ha(i−j)2ni|=|ha2ni|=2,wehavean/2=(ai−j)n/2.Foreach1≤ℓ≤n2 letMℓ= (xy)ℓ,(xy)ℓ+n/2 andT = y(xy)ℓ,y(xy)ℓ+n/2 . NotethatM 6=M andT 6=T foreachs6=k. Also, eachM isan ℓ s k s k (cid:8) ℓ (cid:9) edgeinCay(D ,S)because 2n (cid:8) (cid:9) (xy)ℓ+n/2(xy)−ℓ=(xy)n/2=(ai−j)n/2=an/2∈S Thus,{M1,M2,...,Mn}isamatchinginX(Dn,S).Similarly,{T1,T2,...,Tn}isamatchingandhence, 2 2 {M1,M2,...,Mn,T1,T2,...,Tn}providesaperfectmatchingforCay(D2n,S).Therefore,wehaveacy- 2 2 cleon2nverticesinwhichitsoppositepairsofverticesareadjacent(seeFigure1(i)). Thisimplies thatCay(D ,S)isaMo¨biusLadderandbyTheorem1.1,dim (Cay(D ,S))6=2. 2n M 2n Subcase2.2. a∈an/2haib,ajbi. Inthiscase,thereexistsk∈Zsuchthata=an2(ai−j)k. Hence,a2n+1∈hai−jianda2=(an2+1)2 ∈ hai−ji. Thus,|hai−ji|≥|ha2i|= n.Hence,O(ai−j)= n orO(ai−j)=n.ThesituationO(ai−j)=nis 2 2 consideredinSubcase2.1andwecanassumethatO(xy)=O(ai−j)=n/2. Therefore,Cay(D ,S) 2n containstwon-cyclesasbelow. e∼y∼xy∼yxy∼(xy)2∼y(xy)2∼...∼y(xy)n/2−1∼(xy)n/2=e, an/2∼yan/2∼(xy)an/2∼y(xy)an/2∼(xy)2an/2∼...∼(xy)n/2an/2=an/2. The fact O(xy)=n/2 implies that n vertices apeared in each cycle are distinct. Also, using the appearenceofb,itiseasytoseethat(xy)t 6=y(xy)san2 andy(xy)t6=(xy)sa2n foreacht,s∈Z. Ifthere existt,s∈Zsuchthat(xy)t =(xy)sa2n ory(xy)t =y(xy)san2,thena2n =(ai−j)(t−s)∈hai−ji=ha2i. 4 Thus,4|nwhichisacontradiction(seeLemma2.2). Therefore,allof2nverticesappearedinthese n cyclesaredistinct.Sincea2 ∈S,correspondingverticesoftwocyclesareadjacent(seeFigure1(ii)). Hence,Cay(D ,S)isisomorphictoP ×C andTheorem1.2impliesthatdim (Cay(D ,S))=3. 2n 2 n M 2n Case3. S={aib,ajb,atb}. LetH =haiandhence,V(Cay(D ,S))=H∪Hb. Ifas,at ∈H, thenasa−t =as−t ∈/ S. Thus,the 2n subsetH ofverticesinducesanindependentsetinCay(D ,S). Similarly,Hbisanindependentset. 2n Consequently,Cay(D ,S) is a 3-regularbipartite graph on 2n vertices. Now Lemma 2.3 implies 2n thatdim(Cay(D ,S))isatleastthree.Thiscompletestheproof. 2n un/2 yxy xy y(xy)n/2−1un/2 yun/2 (xy)2 y e y(xy)n/2−1 y (xy)n/2 e (xy)n/2−1un/2 (xy)n/2−1 xy xyun/2 yxy y(xy)n/2 (xy)n/2+2 (xy)n/2+1 y(xy)n/2+1 yxyun/2 (i) (ii) Figure1:(i)AMo¨biusLaddergraph,and(ii)theCartesianproductP2×Cn. Corollary2.5. IfS⊆D suchthate∈/S=S−1and|S|≥4,thendim (Cay(D ,S))≥3. 2n M 2n Wedeclarethatwehavenocompetinginterests References [1] M. Ali, G. Ali, M. Imran, A. Q. Baig, M. K.f Shafiq, On the metric dimension of Mobius ladders,ArsCombinatoria,105(2012)103-410. [2] Z. Beerliova, F. Eberhard,T. Erlebach, A. Hall, M. Hoffmann,M. Mihal’ak, L.S. Ram, Net- workdicoveryandverification,IEEEJournalOnSelectedAreasinCommunications,24(12) (2006)2168-2181. [3] A. Behtoei, A. Davoodi, M. Jannesari, B. Omoomi, A characterization of some graphs with metricdimensiontwo,submitted,https://arxiv.org/abs/1509.02129. [4] J. Caceres, C. Hernando,M. Mora, I.M.Pelayo, M.L.Puertas, C. Seara, D.R. Wood, On the metricdimensionofcartesianproductsofgraphs,SIAMJournalonDiscreteMathematics,21 (2)(2007)423-441. 5 [5] V.Chva´tal,Mastermind,Combinatorica,3(1983)325-329. [6] G.Chartrand,L.Eroh,M.A.Johnson,O.R.Ollermann,Resolvabilityingraphsandthemetric dimensionofagraph,DiscreteAppliedMathematics,105(2000)99-113. [7] D.Eppstein,Parallelrecognitionofseries-parallelgraphs,InformationandComputation,98(1) (1992)41-55. [8] M.Feng,X.Ma,K.Wang,Thestructureandmetricdimensionofthepowergraphofafinite group,EuropeanJournalofCombinatorics,43(2015)82-97. [9] F.Harary,R.A.Melter,Onthemetricdimensionofagraph,ArsCombinatoria,2(1976)191- 195. [10] M. Janessari, B. Omoomi, Characterization of n-vertex graphs with metric dimension n−3, MathematicaBohemica,139(1)(2014)1-23. [11] S.Khuller,B.Raghavachari,A.Rosenfeld,Landmarksingraphs,DiscreteAppliedMathemat- ics,70(3)(1996)217-229. [12] R.A. Melter, I. Tomescu, Metric bases in digital geometry, Computer Vision Graphics and ImageProcessing,25(1984)113-121. [13] D. Mitsche, J. Roe´, On the limiting distribution of the metric dimension for random forests, EuropeanJournalofCombinatorics,49(2015)68-89. [14] M. Salman, I. Javaid, M. A. Chaudhry, Resolvability in circulant graphs, Acta Mathematica Sinica,EnglishSeries,29(2012)1851-1864. [15] A.SeboandE.Tannier,Onmetricgeneratorsofgraphs,MathematicsofOperationsResearch, 29(2)(2004)383-393. [16] P.J.Slater,Leavesoftrees,CongressusNumerantium,14(1975)549-559. [17] G. Sudhakara, A.R. Hemanth Kumar, Graphs with metric dimension two-a characterization, WorldAcademyofScience,EngineeringandTechnology,36(2009)621-626. [18] E.Vatandoost,A.Behtoei,Y.GolkhandyPour,Cayleygraphswithmetricdimensiontwo-A characterization,submitted,https://arxiv.org/abs/1609.06565. 6