1 Introduction

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

Let G=(V, E) be a graph. For any vertex v∈V(G), N(v) denotes the vertex neighborhood of v in G, d_G(v)=|N(v)| is called the degree of v in G, Δ=Δ(G) and δ=δ(G) denote the maximum degree and minimum degree of G respectively. P_n, C_n and K_n denote the path, cycle and complete graph of order n, respectively, and W_n=C_n∨K₁ denotes the wheel of order n+1. If u, v∈V(G), then d_G(u, v) denotes the distance between u and v in G.

Chartrand^[3] stated the concept of the locating set and locating number of a graph G as follows:

Definition 1  Let G=(V, E) be a connected graph and W={w₁, w₂, …, w_k} be an ordered subset of V(G). For any vertex v∈V, the locating code of v with respect to W is the k-vector C_W(v)={d(v, w₁), d(v, w₂), …, d(v, w_k)}, W is said to be a locating set of G if distinct vertices have the distinct locating code, and the locating number of G is defined as:

$ Loc\left( G \right) = \min \left\{ {\left| W \right|:W\;{\rm{is}}\;{\rm{a}}\;{\rm{locating}}\;{\rm{set}}\;{\rm{of}}\;G} \right\} $

A locating set W of G is 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 graph G, 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.

Lemma 1^[3]  (1) A connected graph G of order n has locating number 1 if and only if G$\cong $P_n;

(2) A connected graph G of order n≥2 has locating number n-1 if and only if G$\cong $K_n.

Lemma 2^[3]   For any graph G of order n with the diameter d, then

$ {\log _3}\left( {\Delta + 1} \right) \le Loc\left( G \right) \le n-d\left( G \right) $

where Δ is the maximum degree of G.

Similarly, let f be a proper k-coloring of a connected graph G and Π=(V₁, V₂, …, V_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple Π(v) =(d(v, V₁), (d(v, V₂), …, (d(v, V_k)), where (d(v, V_i) = min{(d(v, x): x∈V_i}, 1≤i≤k. If distinct vertices have distinct color codes, then f is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, 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 all n≥5. Chartrand^[7] showed that for each integer k with (n+1)/2≤k≤n, there existed such a graph G of order n with χ_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 order n having locatic number n, n-1 and n-2.

Similar to the locating chromatic number of G, 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 of Loc(G) for some special classes of graphs, we also prove that Loc(T)≥Δ-1 holds for all trees T with 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.

Theorem 1  For all trees T with maximum degree Δ≥2, then Loc(T)≥Δ-1, and this bound is sharp.

Proof  It is obvious for Δ≤2. Next we suppose Δ≥3. Suppose, on the contrary, that there exists a tree T with Loc(T)=t≤Δ-2. Let v∈V(T) is a maximum degree vertex, deg(v)=Δ≥3, and W={w₁, w₂, …, w_t} is a minimum locating set of T, let

$ T-v = {T_1} \cup {T_2} \cup \cdots \cup {T_\Delta } $

Since t≤Δ-2, there exist at least two subtrees T_i and T_j such that V(T_i)∩W=ϕ, and V(T_j)∩W=ϕ. Choose two vertices v₁∈V(T_i)∩N(v) and v₂∈V(T_j)∩N(v), obviously, this two locating codes of v₁ and v₂ with respect to W are the same, this is, C_w(v₁)=C_w(v₂), this contradicts that W={w₁, w₂, …, w_t} is a minimum locating set of T. Thus we have Loc(T)≥Δ-1. Next we may construct a tree T with Loc(T)=Δ-1(Δ≥2).

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

Theorem 2  Let G be a connected graph of order n with the diameter d, if Loc(G)=k, then we have d^k+k≥n.

Proof  Let W={w₁, w₂, …, w_k} be a minimum locating set of G, and V₁=V(G)-W. For every vertex v∈V₁, C_W(v)={(d(v, w₁), (d(v, w₂), …, (d(v, w_k)} is the locating code of v, where 1≤(d(v, w_i)≤d(1≤i≤k). Since distinct vertices of V₁ have distinct locating code, |V₁|≤d^k, and thus n=|V(G)|=|V₁|+|W|≤d^k+k. We have completed the proof of Theorem 2.

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

Theorem 3   (1) For all integers n≥3, then Loc(C_n)=2;(2)Loc(W₄)=Loc(W₅)=2, and Loc(W₃)=Loc(W₆)=3;(3)When n≥7, Loc(W_n)=⌈(2n-2)/5⌉.

Proof  (1) By Lemma 1 (1), we have Loc(C_n)≥2. On the other hand, we may choose any two adjacent vertices w₁ and w₂, it is easy to see that W={w₁, w₂} is a locating set of C_n, and thus Loc(C_n)≤|W|=2, so we have Loc(C_n)=2.

(2) By Lemma 1 (2), Loc(W₃)=Loc(K₄)=3. When n∈{4, 5, 6}, a minimum locating set W of W_n is shown in Fig. 2. Where W={a, b} or W={a, b, c}.

(3) When n=7 or 8, a minimum locating set W={a, b, c} of W_n is shown in Fig. 3.

When n≥9, let W_n=C_n∨K₁, and W={w₁, w₂, …, w_k} be a minimum locating set of W_n, this is, k=Loc(W_n). Let S=V(C_n)∩W, C_n-S=P¹∪P²∪…∪P^t, where t≤|S|≤k, and every Pⁱ is a path of order n_i(1≤i≤t).

For any vertex u∈S, there exists at least one vertex v∈S such that d_Cn(u, v)≤2 (otherwise, let u₁ and u₂ be the adjacent vertices of u in C_n, then we have C_W(u₁)=C_W(u₂), a contradiction). In all paths Pⁱ, every n_i≤3(1≤i≤t), and there is at least one path containing three vertices (otherwise, there exist two vertices u₁ and u₂ in C_n, such C_W(u₁)=C_W(u₂), a contradiction). Thus, in all paths Pⁱ, 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

$ \begin{array}{l} n = \left| S \right| = \sum\limits_{i = 1}^t {{n_i} \le } \left| S \right| + \left\lceil {\frac{t}{2}} \right\rceil = 2\left( {\left\lfloor {\frac{t}{2}} \right\rfloor-1} \right) + \\ \;\;\;\;\;3 \le \frac{{5k}}{2} + 1 \end{array} $

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

Since k is an integer, thus Loc(W_n)=k≥「(2n-2)/5⌉.

On the other hand, we may choose a locating set of W_n=C_n∨K₁ as follows:

Let V(C_n)={v₁, v₂, …, v_n}, v_iv_i+1∈E(C_n)(1≤i≤n-1) and v₁v_n∈E(C_n), V(K₁)={v₀} and v₀v_i∈E(W_n)(1≤i≤n). Let

$ \begin{array}{*{20}{c}} {{M_1}{\rm{ = }}\left\{ {{v_{n-1}}, {v_1}, {v_5}, {v_7}} \right\}}\\ {{M_2} = \left\{ {{v_{5 + 5i}}\left| {1 \le i \le \frac{{n-7}}{5}} \right.} \right\}}\\ {{M_3} = \left\{ {{v_{7 + 5i}}\left| {1 \le i \le \frac{{n-9}}{5}} \right.} \right\}} \end{array} $

And let W=M₁∪M₂∪M₃, it is easy to see that W is a locating set of W_n, and

$ \begin{array}{l} \left| W \right| = 4 + \left\lfloor {\frac{{n-7}}{5}} \right\rfloor + \left\lfloor {\frac{{n-9}}{5}} \right\rfloor = \left\lfloor {\frac{{2n + 2}}{5}} \right\rfloor = \\ \;\;\;\;\;\;\;\;\left\lceil {\frac{{\left( {2n-2} \right)}}{5}} \right\rceil \end{array} $

thus we have

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

Theorem 4   For any complete t-partite graph G=K(n₁, n₂, …, n_t) of order n, if n₁≥n₂≥…≥n_t≥2, then Loc(T)=n-t.

Proof  Let V(G)=V₁∪V₂∪…∪V_t be the t-partite vertex set of G, where |V_i|=n_i (1≤i≤t), Loc(G)=k and W={w₁, w₂, …, w_k} is a minimum locating set of G. For every i∈{1, 2, …, t}, then |V_i∩W|≥n_i-1. Otherwise, there exists integer j(1≤j≤t)such that |V_j∩W|≤n_j-2, then for any two vertices u, v∈(V_j-V_j∩W), we have C_W(u)=C_W(v), a contradiction. Thus |V_i∩W|≥n_i-1 hold for every i∈{1, 2, …, t}, so we have

$ \begin{array}{l} Loc\left( G \right) = k = \left| W \right| = \sum\limits_{i = 1}^t {\left| {{V_i} \cap W} \right| \ge } \sum\limits_{i = 1}^t {\left( {{n_i}-} \right.} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. 1 \right) = n-t \end{array} $

On the other hand, for every integer i∈{1, 2, …, t}, let v_i∈V_i, and W=V-{v₁, v₂, …, v_t}, obviously, W is a locating set of G, thus Loc(G)=k≤|W|=n-t. We have completed the proof of Theorem 4.

Theorem 5   For any two integers m and n, m≥n≥2, then Loc(P_m×P_n)=2.

Proof  By Lemma 1, we have Loc(P_m×P_n)≥2. On the other hand, we may choose two vertices u and v of degree two such that the distance d(u, v)=n-1 in P_m×P_n. Obviously, W={u, v} is a locating set of P_m×P_n, Thus, Loc (P_m×P_n)≤|W|=2. So, we have Loc(P_m×P_n)=2. We have completed the proof of Theorem 5.