Baogen Xu, Chunhua Li and Zhizhu Fan

(Department of Mathematics, East China Jiaotong University, Nanchang, Jiangxi 330013, China)

1 Introduction

For the terminology and notations not defined here, we adopt those in Bondy[1]and Haynes[2]and consider simple graphs only.

LetG=(V,E) be a graph. For any vertexv∈V(G),N(v) denotes the vertex neighborhood ofvinG,dG(v)=|N(v)| is called the degree ofvinG,Δ=Δ(G) andδ=δ(G) denote the maximum degree and minimum degree ofGrespectively.Pn,CnandKndenote the path, cycle and complete graph of ordern, respectively, andWn=Cn∨K1denotes the wheel of ordern+1. Ifu,v∈V(G), thendG(u,v) denotes the distance betweenuandvinG.

Chartrand[3]stated the concept of the locating set and locating number of a graphGas follows:

Definition1LetG=(V,E) be a connected graph andW={w1,w2,…,wk} be an ordered subset ofV(G). For any vertexv∈V, the locating code ofvwith respect toWis thek-vectorCW(v)={d(v,w1),d(v,w2),…,d(v,wk)},Wis said to be a locating set ofGif distinct vertices have the distinct locating code, and the locating number ofGis defined as:

Loc(G)=min{|W|:Wis a locating set ofG}

A locating setWofGis said to be a minimum locating set if |W|=Loc(G).

The locating problem of graphs has been applied to various fields, such as network security, fire and burglary prevention, transportation and oil exploration. For example, in a complex network structure (as a graph), the individual nodes may be damaged, thus affecting the entire network of information transmission. Testing all the nodes in the network requires a large amount of engineering. So, it’s necessary to select some specific nodes (as few as possible) and to position the positioner. The distances from each node to those specific nodes can be arranged into an order for a locating code (different nodes have different locating codes). The shortest length of the locating code is the locating number of graphG, which is also the number of the fewest locators needed.

Raja[4]discussed the relations between locating number, domination number, clique number and chromatic number of a graph. Chartrand[3]obtained the following two results.

Lemma1[3](1) A connected graphGof ordernhas locating number 1 if and only ifG?Pn;

(2) A connected graphGof ordern≥2 has locating numbern-1 if and only ifG?Kn.

Lemma2[3]For any graphGof ordernwith the diameterd, then

log3(Δ+1)≤Loc(G)≤n-d(G)

whereΔis the maximum degree ofG.

Similarly , letfbe a properk-coloring of a connected graphGandΠ=(V1,V2,… ,Vk) be an ordered partition ofV(G) into the resulting color classes. For a vertexvofG, the color code ofvwith respect toΠis defined to be the orderedk-tupleΠ(v) =(d(v,V1),d(v,V2), … ,d(v,Vk)), whered(v,Vi) = min{d(v,x):x∈Vi}, 1≤i≤k. If distinct vertices have distinct color codes, thenfis called a locating coloring. The minimum number of colors needed in a locating coloring ofGis the locating chromatic number ofG, denoted byχL(G).

Behtoei and Anbarloei[5]studied the locating chromatic number of the join of graphs, determined the locating chromatic number of the join of paths, cycles and complete multipartite graphs. Behtoei and Omoomi[6]studied the locating chromatic number of Kneser graphs, and showed thatχL(KG(n,2))=n-1 for alln≥5. Chartrand[7]showed that for each integerkwith (n+1)/2≤k≤n, there existed such a graphGof ordernwithχL(G)=k. Asmiati[8]determined the locating-chromatic numbers of non-homogeneous caterpillars and firecracker graphs. Salman and Chaudhry[9]studied the locatic number of paths, cycles and characterize all the connected graphs of ordernhaving locatic numbern,n-1 andn-2.

Similar to the locating chromatic number ofG, Foucaud and Henning[10-11]studied the locating domination set and locating domination numbers of graphs, obtained some bounds for general graphs, and determined the locating domination numbers for some special graphs. Fazil[12]studied the locating domination set of hypergraphs, and Xing[13]defined the conception of locating total domination in graphs, and determined the locating total domination number of the Cartesian product of cycles and paths.

In this paper, we obtain some bounds for the locating numbers of graphs, and determine the exact value ofLoc(G) for some special classes of graphs, we also prove thatLoc(T)≥Δ-1 holds for all treesTwith maximum degreeΔ, and show that this lower bound is the best possible.

2 Main Results

First, we give a sharp lower bound of the locating numbers for all trees with maximum degreeΔ≥2.

Theorem1For all treesTwith maximum degreeΔ≥2, thenLoc(T)≥Δ-1, and this bound is sharp.

ProofIt is obvious forΔ≤2. Next we supposeΔ≥3. Suppose, on the contrary, that there exists a treeTwithLoc(T)=t≤Δ-2. Letv∈V(T) is a maximum degree vertex, deg(v)=Δ≥3, andW={w1,w2,…,wt} is a minimum locating set ofT, let

T-v=T1∪T2∪…∪TΔ

Sincet≤Δ-2, there exist at least two subtreesTiandTjsuch thatV(Ti)∩W=φ, andV(Tj)∩W=φ. Choose two verticesv1∈V(Ti)∩N(v) andv2∈V(Tj)∩N(v),obviously, this two locating codes ofv1andv2with respect toWare the same, this is,Cw(v1)=Cw(v2), this contradicts thatW={w1,w2,…,wt} is a minimum locating set ofT. Thus we haveLoc(T)≥Δ-1. Next we may construct a treeTwithLoc(T)=Δ-1(Δ≥2).

Obviously,W={1,2,…,t-1} in Fig.1 is a locating set ofT. We have completed the proof of Theorem 1.

Fig.1 A tree T with Loc(T)=t-1 where t=Δ

Theorem2LetGbe a connected graph of ordernwith the diameterd, ifLoc(G)=k, then we havedk+k≥n.

ProofLetW={w1,w2,…,wk} be a minimum locating set ofG, andV1=V(G)-W. For every vertexv∈V1,CW(v)={d(v,w1),d(v,w2),…,d(v,wk)} is the locating code ofv, where 1≤d(v,wi)≤d(1≤i≤k). Since distinct vertices ofV1have distinct locating code, |V1|≤dk, and thusn=|V(G)|=|V1|+|W|≤dk+k. We have completed the proof of Theorem 2.

Next we consider the locating numbers for several kinds of special graphs.

Theorem3(1) For all integersn≥3, thenLoc(Cn)=2;(2)Loc(W4)=Loc(W5)=2, andLoc(W3)=Loc(W6)=3;(3)Whenn≥7,Loc(Wn)=「(2n-2)/5?.

Proof(1) By Lemma 1 (1),we haveLoc(Cn)≥2 . On the other hand, we may choose any two adjacent verticesw1andw2, it is easy to see thatW={w1,w2} is a locating set ofCn, and thusLoc(Cn)≤|W|=2, so we haveLoc(Cn)=2.

(2) By Lemma 1 (2),Loc(W3)=Loc(K4)=3. Whenn∈{4,5,6}, a minimum locating setWofWnis shown in Fig. 2. WhereW={a,b} orW={a,b,c}. (3) Whenn=7 or 8, a minimum locating setW={a,b,c} ofWnis shown in Fig.3.

Whenn≥9，letWn=Cn∨K1, andW={w1,w2,…,wk} be a minimum locating set ofWn, this is,k=Loc(Wn). LetS=V(Cn)∩W,Cn-S=P1∪P2∪…∪Pt, wheret≤|S|≤k, and everyPiis a path of orderni(1≤i≤t).

Fig.2 A minimum locating set W of Wn when n∈{4,5,6}

Fig.3 A minimum locating set W={a,b,c} of Wn when n∈{7,8}

For any vertexu∈S, there exists at least one vertexv∈Ssuch thatdCn(u,v)≤2 (otherwise, letu1andu2be the adjacent vertices ofuinCn, then we haveCW(u1)=CW(u2), a contradiction). In all pathsPi, everyni≤3(1≤i≤t), and there is at least one path containing three vertices (otherwise, there exist two verticesu1andu2inCn,suchCW(u1)=CW(u2), a contradiction). Thus, in all pathsPi, there are at least 「t/2? paths containing one vertex, there are at most ?t/2」 paths containing two or three vertices, so, we have

this is ,Loc(Wn)=k≥(2n-2)/5.

Sincekis an integer, thusLoc(Wn)=k≥「(2n-2)/5?.

On the other hand, we may choose a locating set ofWn=Cn∨K1as follows:

LetV(Cn)={v1,v2,…,vn},vivi+1∈E(Cn)(1≤i≤n-1) andv1vn∈E(Cn),V(K1)={v0} andv0vi∈E(Wn)(1≤i≤n). Let

M1={vn-1,v1,v5,v7}

And letW=M1∪M2∪M3, it is easy to see thatWis a locating set ofWn, and

thus we have

Loc(Wn)≤|W|=「2n-2/5?, we have completed the proof of Theorem 3.

Theorem4For any completet- partite graphG=K(n1,n2,…,nt) of ordern, ifn1≥n2≥…≥nt≥2, thenLoc(T)=n-t.

ProofLetV(G)=V1∪V2∪…∪Vtbe thet- partite vertex set ofG, where |Vi|=ni(1≤i≤t),Loc(G)=kandW={w1,w2,…,wk} is a minimum locating set ofG. For everyi∈{1,2,…,t}, then |Vi∩W|≥ni-1. Otherwise, there exists integerj(1≤j≤t)such that |Vj∩W|≤nj-2, then for any two verticesu,v∈(Vj-Vj∩W), we haveCW(u)=CW(v), a contradiction. Thus |Vi∩W|≥ni-1 hold for everyi∈{1,2,…,t}, so we have

On the other hand, for every integeri∈{1,2,…,t}, letvi∈Vi, andW=V-{v1,v2,…,vt}, obviously,Wis a locating set ofG, thusLoc(G)=k≤|W|=n-t. We have completed the proof of Theorem 4.

Theorem5For any two integersmandn,m≥n≥2, thenLoc(Pm×Pn)=2.

ProofBy Lemma 1, we haveLoc(Pm×Pn)≥2. On the other hand, we may choose two verticesuandvof degree two such that the distanced(u,v)=n-1 inPm×Pn. Obviously,W={u,v} is a locating set ofPm×Pn, Thus,Loc(Pm×Pn)≤|W|=2. So, we haveLoc(Pm×Pn)=2. We have completed the proof of Theorem 5.

[1]Bondy J A, Murty U S R. Graph Theory with Application. Amsterdam:Elsevier , 1976.

[2]Haynes T W, Hedetniemi S T, Slater P J. Domination in Graph. New York:Marcel Dekker, Inc., 1998.

[3]Chartrand G, Zhang P. Introduction to Graph Theory. Boston:The McGraw-Hill Companies,Inc. 2006. 341-346.

[4]Raja R ,Pirzada S, Redmond S. On locating numbers and codes of zero divisor graphs associated with commutative rings. Journal of Algebra and Its Applications, 2016, 15(1): 1650-1664.DOI:10.1142/S0219498816500146.

[5]Behtoei A, Anbarloei M. The locating chromatic number of the join of graphs. Bulletin of the Iranian Mathematical Society, 2014, 40(6): 1491-1501.

[6]Behtoei A, Omoomi B. On the locating chromatic number of Kneser graphs. Discrete Applied Mathematics, 2011, 159(18): 2214-2221.DOI: 10.1016/j.dam.2011.07.015.

[7]Chartrand G, Erwin D, Henning M A, et al. Graphs of ordernwith locating-chromatic numbern-1. Discrete Mathematics, 2003, 269(1-3): 65-72.DOI: 10.1016/S0012-365X(02)00829-4.

[8]Asmiati A. On the locating chromatic numbers of non-homogeneous caterpillars and firecracker graphs. Far East Journal of Mathematical Sciences, 2016, 100(8): 1305-1316.

[9]Salman M, Chaudhry M A,Javaid I. On the locatic number of graphs. International Journal of Computer Mathematics, 2013, 90(5): 912-920.DOI: 10.1080/00207160.2012.749346.

[10]Foucaud F, Henning M A. Location-domination and matching in cubic graphs. Discrete Mathematics, 2016, 339(4): 1221-1231.DOI: 10.1016/j.disc.2015.11.016.

[11]Foucaud F, Henning M A, L?wenstein C, et al. Locating-dominating sets in twin-free graphs. Discrete Applied Mathematics, 2016, 200(1): 52-58.DOI: 10.1016/j.dam.2015.06.038.

[12]Fazil M, Javaid I, Salman M, et al. Locating-dominating sets in hypergraphs. Periodica Mathematica Hungarica, 2016,72(2): 224-234.

[13]Xing H, Sohn M Y. Bounds on locating total domination number of the Cartesian product of cycles and paths. Information Processing Letters, 2015, 115(12): 950-956.DOI:10.1016/j.ipl.2015.07.010.