Multiplicative Distance-Location Number of Graphs

KM. Kathiresan1, S. Jeyagermani1
1Department of Mathematics, Ayya Nadar Janaki Ammal College, Sivakasi, India

Abstract

For a set S of vertices in a connected graph G, the multiplicative distance of a vertex v with respect to S is defined by dS(v)=xS,xvd(v,x). If dS(u)dS(v) for each pair u,v of distinct vertices of G, then S is called a multiplicative distance-locating set of G. The minimum cardinality of a multiplicative distance-locating set of G is called its multiplicative distance-location number locd(G). If dS(u)dS(v) for each pair u,v of distinct vertices of GS, then S is called an external multiplicative distance-locating set of G. The minimum cardinality of an external multiplicative distance-locating set of G is called its external multiplicative location number loce(G). We prove the existence or non-existence of multiplicative distance-locating sets in some well-known classes of connected graphs. Also, we introduce a family of connected graphs such that locd(G) exists. Moreover, there are infinite classes of connected graphs G for which locd(G) exists as well as infinite classes of connected graphs G for which locd(G) does not exist. A lower bound for the multiplicative distance-location number of a connected graph is established in terms of its order and diameter.

Keywords: Distance, locating set, Distance-locating set, Distance-location number, Multiplicative distance-locating set, Multiplicative distance-location number

1. Introduction

Let G be a connected graph and let W={w1,w2,,wk} be an ordered set of vertices in G. If vV(G), the k-vector CW(v) of v with respect to W is defined by CW(v)=(d(v,w1),d(v,w2),,d(v,wk)) where d(v,wi) is the distance between v and wi (1ik). The set W is called a locating set if for every pair of distinct vertices u,vV(G), CW(u)CW(v). It is also called a resolving set. The k-vector CW(v) is called the locating code of v with respect to W. The cardinality of a minimum locating set in G is called the location number of G and it is denoted by loc(G). In 1975 and later in 1988, Slater [1,2] introduced the concept of “Locating Set” of a graph G. Independently, in 1976, Harary and Melter [3] discovered these concepts as well but used the term Metric Dimension, rather than location number. Let S be a subset of V(G). The distance of a vertex v with respect to S is defined by dS(v)=xsxvd(v,x).

If dS(u)dS(v) for each pair u,v of distinct vertices of G, then S is called a distance-locating set of G. In 2003, Chartrand et al. [4] defined the concept “Distance-Locating Set” of a graph G and the minimum cardinality of a distance-locating set of G is the distance-location number locd(G). They found the relationship between loc(G) and locd(G). Further, they found the existence of distance-locating sets in some well-known classes of connected graphs and proved that no distance-locating set in a connected graph G has cardinality 2 or 3.

Moreover, there are infinite classes of connected graphs G for which locd(G) exists as well as infinite classes of connected graphs G for which locd(G) doest not exist. Also, they found the lower bound for the distance-location number of a connected graph in terms of its order and diameter.

Motivated by the concept Distance-Locating Set of a graph G, we introduce the new concept “Multiplicative Distance-Locating Set” of a graph G and we define the cardinality of a minimum multiplicative distance-locating set of G as the multiplicative distance-location number locd(G). Then we find the relationship between loc(G) and locd(G). Also, we find the existence of multiplicative distance-locating sets in some well-known classes of connected graphs and we prove that no multiplicative distance-locating set in a connected graph G has cardinality 2. Moreover, we find an infinite classes of connected graphs such as complete graph and star graph for which locd(G) does not exist. Also, we find that the path P3 is the only connected graph G of diameter 2 such that locd(G) exists. We define the new class of connected graph PnCm, obtained by identifying any two consecutive vertices of Cm with the (n2)th and (n1)th vertices of Pn, for which locd(G) exists. Also, we find the lower bound for the multiplicative distance-location number of a connected graph in terms of its order and diameter.

Chartrand et al. [4] defined the concept External Distance-Locating Set of G and the cardinality of a minimum external distance-locating set of G is the external location number loce(G). Further, they found the relationship between loc(G),locd(G) and locd(G) and studied the external location number of some well-known classes of connected graphs.

Motivated by the concept External Distance-Locating Set of a graph G, we introduce the new concept “External Multiplicative Distance-Locating Set” of a graph G and the cardinality of a minimum external multiplicative distance-locating set of G is the external multiplicative location number loce(G). Further, we find the external multiplicative location number of some well-known classes of connected graphs. Also, we introduce the new concept “Magic Locating Set” of a graph G and we determine the magic location number of some well-known classes of connected graphs.

2. The Multiplicative Distance-Location Number

For a set S of vertices in a connected graph G, the multiplicative distance of a vertex v in V with respect to S is defined by dS(v)=xS,xvd(v,x). If S={v}, then we assign 0 to dS(v). If dS(u)dS(v) for each pair u,v of distinct vertices of G, then S is called a multiplicative distance-locating set of G. A minimum multiplicative distance-locating set of G is a multiplicative distance-locating set of minimum cardinality and this cardinality is the multiplicative distance-location number locd(G). The following results describe a relationship between locd(G) and loc(G).

Proposition 1. Every multiplicative distance-locating set of a graph is a locating set.

Proof. On the contrary, assume that the multiplicative distance-locating set S={w1,w2,,wk} is not a locating set. Then there exists two distinct vertices u,vV(G) such that CS(u)=CS(v). That is, (d(u,w1),d(u,w2), ,d(u,wk))=(d(v,w1,d(v,w2),,d(v,wk)). Then wiSd(u,wi)=wiSd(v,wi). Therefore dS(u)=dS(v), which is a contradiction to the fact that S is a multiplicative distance-locating set of G◻

Corollary 1. If G is a connected graph such that locd(G) exists, then loc(G)locd(G).

The following Theorem 1 shows that the path Pn is the only connected graph of order n with locd(G)=1.

Theorem 1. Let G be a connected graph of order n2. Then locd(G)=1 if and only if G=Pn.

Proof. Let G=Pn:v1,v2,,vn be a path on n vertices. Since d(vi,v1)=i1 for 1in, {v1} is a minimum multiplicative distance-locating set of Pn. Therefore, locd(G)=1. Conversely, suppose locd(G)=1. Let S={w} be a minimum multiplicative distance-locating set for G. Then dS(v)=d(v,w) for each vertex v of G is a non-negative integer less than n. Since dS(v), vV(G) are distinct, there exists a vertex u in G such that d(u,w)=n1. Consequently the diameter of G is n1. Hence G=Pn◻

Proposition 2. No multiplicative distance-locating set in a connected graph G consists of two vertices of G.

Proof. Suppose S={u,v} is a multiplicative distance-locating set for G. Then dS(u)=d(u,v)=dS(v), which is a contradiction. ◻

In the case of distance-locating set of a graph G, there is no distance-locating set with exactly three vertices of G for any graph G. However, multiplicative distance-locating set of a graph may consists of three vertices of G. For example, for the following graph G,

S={v1,v2,v7} is a minimum multiplicative distance locating set and hence locd(G)=3. In order to give examples of other graphs G for which locd(G) does not exist, we now make some observations. In a graph G, the nieghbourhood of a vertex v in G is the set N(v) consisting of all vertices which are adjacent to v. The closed neighbourhood is N[v]=N(v){v}

Proposition 3. If u and v are distinct vertices of a connected graph G such that either N(u)=N(v) or N[u]=N[v], then every multiplicative distance-locating set of G contains exactly one of u and v.

Proof. Let u,vG and uv. Suppose S is a multiplicative distance-locating set for G.
Case 1. Suppose N(u)=N(v).

If u,vS, then u and v are having the same distance apart from each vertex of G. Therefore,dS(u)=dS(v) , which is a contradiction to the fact that S is a multiplicative distance-locating set. Similar proof holds when u,vS.
Case 2. Suppose N[u]=N[v].

The proof is similar to the case 1. ◻

Corollary 2. If G is a connected graph containing three distinct vertices u, v and w such that either N(u)=N(v)=N(w) or N[u]=N[v]=N[w], then locd(G) does not exist.

In a graph G, if degv=1, then v is called an end-vertex.

Corollary 3. If G is a connected graph such that locd(G) exists, then every vertex of G is adjacent to at most two end-vertices.

The converse of Corollary 3 does not necessarily hold. For example, in the following graph G every vertex of G is adjacent to at most two end vertices, but locd(G) does not exist.

We have verified this fact by considering all possible cases.

Corollary 4. If n3, then locd(Kn) and locd(K1,n) do not exist.

Proof. Immediately follows from Corollaries 2 and 3. ◻

Next we show that the path P3 is the only connected graph G of diameter 2 such that locd(G) exists.

Theorem 2. If G is a connected graph of diameter 2 for which locd(G) exists, then G=P3.

Proof. Let S be a minimum multiplicative distance-locating set for G and let |S|=k. Suppose k=1. Since diameter of G is 2 and |S|=1, by Theorem 1, G=P3. By Proposition 2, k2. Suppose k=3. Let S={u,v,w}. Then dS(u)=d(u,v)×d(u,w), dS(v)=d(u,v)×d(v,w) and dS(w)=d(u,w)×d(v,w). Since S is a multiplicative distance-locating set, dS(u)dS(v) and hence d(u,w)d(v,w). Since diameter of G is 2, without loss of generality, we may assume that d(u,w)=1, d(v,w)=2. Then dS(u)=d(u,v), dS(v)=2d(u,v) and dS(w)=2 Since G has diameter 2, either d(u,v)=1 or d(u,v)=2. If d(u,v)=1, then dS(v)=2. Therefore, dS(v)=dS(w), which is a contradiction. If d(u,v)=2, then dS(u)=2. Therefore, dS(u)=dS(w), which is a contradiction. Thus, S is not a multiplicative distance-locating set for G. Hence assume that k4. Let H=S be the subgraph of G induced by S. Since G has diameter 2, for each vV(H)=S, it follows that dS(v) is uniquely determined by kdegH(v) vertices of S since dH(u,v)=1 for the vertices u which are adjacent to v. Since H is nontrivial and diameter of G is 2, H contains at least two vertices x and y such that degH(x)=degH(y). Suppose degH(x)=degH(y)=a. Since G has diameter 2, dS(x)=2ka1 and dS(y)=2ka1. Hence S is not a multiplicative distance-locating set for k4◻

A graph G is a k-partite graph if V(G) can be partitioned into k subsets V1,V2,,Vk such that uv is an edge of G if u and v are belong to different partite sets. If, in addition, every two vertices in different partite sets are joined by an edge, then G is a complete k-partite graph. If |Vi|=ni for 1ik, then we denote this complete k-partite graph by Kn1,n2,,nk. The complete k-partite graphs are aslo referred to as complete multiplartite graphs.

The following result provides another well-known class of graphs for which locd(G) does not exist.

Corollary 5. If G is a complete multipartite graph of order at least 4 that is not complete, then locd(G) does not exist.

Now, we define a family of connected graph PnCm such that locd(G) exists.

Definition 1. Let Pn be a path on n vertices and let Cm be a cycle on m vertices. The graph PnCm is obtained by identifying any two consecutive vertices of Cm with the (n2)th and (n1)th vertices of Pn as shown in the following Figure 1,

Figure 1

Theorem 3. For n>4, m3, locd(PnCm)4.

Proof. Case 1. Suppose m is even, m=2k. Let {v1,v2,,vn,u1,u2,,uk1,w1,w2,wk1} be the vertices of PnCm as shown in the above Figure 1.

Let S={vn,vn2,vn3,vn4} be a subset of the vertex set of PnCm. Then dS(vi)=d(vi,vn)×d(vi,vn2)×d(vi,vn3)×d(vi,vn4),for1in5=(ni)(ni2)(ni3)(ni4).dS(ui)=d(ui,vn)×d(ui,vn2)×d(ui,vn3)×d(ui,vn4),for1ik1=i(i+1)(i+2)2.dS(wi)=d(wi,vn)×d(wi,vn2)×d(wi,vn3)×d(wi,vn4),for1ik1=(i+1)2(i+2)(i+3).dS(vn4)=d(vn4,vn)×d(vn4,vn2)×d(vn4,vn3)=4×2×1=8.dS(vn3)=d(vn3,vn)×d(vn3,vn2)×d(vn3,vn4)=3×1×1=3.dS(vn2)=d(vn2,vn)×d(vn2,vn3)×d(vn2,vn4)=2×1×2=4.dS(vn1)=d(vn1,vn)×d(vn1,vn2)×d(vn1,vn3)×d(vn1,vn4)=1×1×2×3=6.dS(vn)=d(vn,vn2)×d(vn,vn3)×d(vn,vn4)=2×3×4=24. Certainly, dS(vi)dS(vj) for each pair i, j of distinct integers 1i,jn5 and dS(ui)dS(uj) and dS(wi)dS(wj) for each pair i,j of distinct integers 1i,jk1. Since min{dS(vi):1in5,n>5}=30 and max{dS(vi):n4in}=24, dS(vi)dS(vj) for each pair i, j of distinct integers 1i,jn. The factors of dS(vi), dS(ui) and dS(wi) are: dS(vi)=x(x+1)(x+2)(x+4) where x=ni4, dS(ui)=y(y+1)(y+2)2 where y=i and dS(wi)=z2(z+1)(z+2) where z=i+1.

We claim that dS(vi)dS(uj) for every two integers 1in, 1jk1. First we discuss when i varies from 1 to n5 and j varies from 1 to k1. If y<x2 or y>x+4,then dS(vi)dS(uj). We consider the following cases:

  1. Suppose dS(vi)=dS(uj). Then x(x+1)(x+2)(x+4)=y(y+1)(y+2)2

    • (a) Suppose y=x2. Then x(x+1)(x+2)(x+4)=(x2)(x1)x2. This implies (x+1)(x+2)(x+4)=x(x1)(x2), which is a contradiction.

    • (b) Suppose y=x1. Then x(x+1)(x+2)(x+4)=(x1)x(x+1)2. This implies x2+6x+8=x21. Therefore, x=3/2, which is a contradiction to the fact that x is a positive integer.

    • (c) Suppose y=x. Then x(x+1)(x+2)(x+4)=x(x+1)(x+2)2. This implies that 4=2, which is a contradiction.

    • (d) Suppose y=x+1. Then x(x+1)(x+2)(x+4)=(x+1)(x+2)(x+3)2. Hence x=9/2, which is a contradiction.

    • (e) Suppose y=x+2. Then x(x+1)(x+2)(x+4)=(x+2)(x+3)(x+4)2. Thus, x=2, which is a contradiction.

    • (f) Suppose y=x+3. Then x(x+1)(x+2)(x+4)=(x+3)(x+4)(x+5)2. This implies 10x2+53x+75=0. Since b24ac=191<0, it has no real solution, which is a contradiction.

    • (g) Suppose y=x+4. Then x(x+1)(x+2)(x+4)=(x+4)(x+5)(x+6)2. This implies 14x2+94x+180=0. Since b24ac=1244<0, it has no real solution, which is a contradiction.

    Thus, dS(vi)dS(uj) for every two integers 1in5, 1jk1. Since max{dS(vi):n4in}=24 and {dS(uj):1jk1}={18,96,}, dS(vi)dS(uj) for every two integers 1in, 1jk1. Next we claim that dS(vi)dS(wj) for every two integers 1in, 1jk1. First we discuss when i varies from 1 to n5 and j varies from 1 to k1. If z<x2 or z>x+4, then x(x+1)(x+2)(x+4)z2(z+1)(z+2). Therefore, dS(vi)dS(wj).

  2. Suppose dS(vi)=dS(wj). Then x(x+1)(x+2)(x+4)=z2(z+1)(z+2). If x2zx+4, then the proof is similar to the above case. Thus, dS(vi)dS(wj) for every two integers 1in5, 1jk1. Since max{dS(vi):n4in}=24 and min{dS(wj):1jk1}=48, dS(vi)dS(wj) for every two integers 1in, 1jk1. Next we claim that dS(ui)dS(wj) for every two integers 1i,jk1. If z<y3 or z>y+2, then dS(ui)dS(wj).

  3. Suppose dS(ui)=dS(wj). Then y(y+1)(y+2)2=z2(z+1)(z+2). If y3zy+2, then the proof is similar to the first case. Thus, dS(ui)dS(wj) for every two integers 1i,jk1. From the above three cases, dS(u)dS(v) for any two pair of distinct vertices u,v of PnCm. Therefore, S is a multiplicative distance-locating set for PnCm. Hence, locd(PnCm)4 when m is even.

Case 2. Suppose m is odd, m=2k+1.

Let {v1,v2,,vn,u1,u2,,uk1,w1,w2,,wk1,wk} be the vertices of PnCm as shown in the Figure 2.

Figure 2

Let S={vn,vn2,vn3,vn4} be a subset of the vertex set of PnCm. Then dS(vi)=d(vi,vn)×d(vi,vn2)×d(vi,vn3)×(vi,vn4),for1in5=(ni)(ni2)(ni3)(ni4).dS(ui)=d(ui,vn)×d(ui,vn2)×d(ui,vn3)×d(ui,vn4),for1ik1=i(i+1)(i+2)2.dS(wi)=d(wi,vn)×d(wi,vn2)×d(wi,vn3)×d(wi,vn4),for1ik1=(i+1)2(i+2)(i+3).dS(wk)=d(wi,vn)×d(wi,vn2)×d(wi,vn3)×d(wi,vn4)=k(k+1)2(k+2).dS(vn4)=d(vn4,vn)×d(vn4,vn2)×d(vn4,vn3)=4×2×1=8.dS(vn3)=d(vn3,vn)×d(vn3,vn2)×d(vn3,vn4)=3×1×1=3.dS(vn2)=d(vn2,vn)×d(vn2,vn3)×d(vn2,vn4)=2×1×2=4.dS(vn1)=d(vn1,vn)×d(vn1,vn2)×d(vn1,vn3)×d(vn1,vn4)=1×1×2×3=6.dS(vn)=d(vn,vn2)×d(vn,vn3)×d(vn,vn4)=2×3×4=24. By case 1, dS(u)dS(v) for any two pair of distinct vertices u,v of PnCm. Therefore, S is a multiplicative distance-locating set for PnCm. Thus, locd(PnCm)4 for m is odd. Hence locd(PnCm)4◻

Corollary 6. The multiplicative distance location number of PnCm is either 3 or 4.

Proof. Since PnCm is not a path, the proof follows from Theorem 1 and Proposition 2 ◻

Now we establish a lower bound for the multiplicative distance-location number of a connected graph in terms of its order and diameter. Let G be a connected graph of order n. For a subset S of V(G), define

Dmin(S)=min{dS(v):vV(G)},
Dmax(S)=max{dS(v):vV(G)}.

Observation 4. Let G be a connected graph of order n2 and diameter d2. If S is a multiplicative distance-locating set for G with |S|=k, then n1Dmax(S)Dmin(S)dk.

Proof. Suppose S is a multiplicative distance-locating set for G. Then the numbers dS(v),vV(G) are distinct. The set {dS(v):vV(G)} contains n distinct numbers. Therefore, (1)Dmax(S)Dmin(S)n1. Since S is a multiplicative distance-locating set, diamG=d and |S|=k, Dmin(S)0 and Dmax(S)dk. Thus, (2)Dmax(S)Dmin(S)dk. Combining (1) and (2), we get, n1Dmax(S)Dmin(S)dk◻

Observation 5. If G is a connected graph of order n2 and diameter d2 for which locd(G) exists, then locd(G)log(n1)logd.

Proof. Let S be a multiplicative distance-locating set for G and let |S|=k. By Observation 4, n1Dmax(S)Dmin(S)dk. Therefore, n1dk. Thus locd(G)log(n1logd◻

3. The External Multiplicative Location Number of a graph

We shown in Section 2, for many graphs G, locd(G) does not exist. However, there is a closely related parameter that is defined for every graph. For a set S of vertices in a connected graph G, the multiplicative distance of a vertex v with respect to S is defined by dS(v)=xS,xvd(v,x). If dS(u)dS(v) for each pair u,v of distinct vertices of GS, then S is called an external multiplicative distance-locating set of G. The cardinality of a minimum external multiplicative distance-locating set of G is called the external multiplicative location number of G. It is denoted by loce(G).

Proposition 4. Every external multiplicative distance-locating set is a locating set.

Proof. Let S be an external multiplicative distance-locating set for G. Then the numbers dS(v),vV(G)S are distinct. Let u,v be any two distinct vertices of G.

  1. If u,vS, then CS(u)CS(v).

  2. Suppose u,vV(G)S. If CS(u)=CS(v), then dS(u)=dS(v), which is a contradiction. Therefore, CS(u)CS(v).

  3. Suppose uS and vV(G)S. Then the locating code of the vertex u with respect to S, CS(u) contains the zero vector. Since vV(G)S, CS(v) does not contain the zero vector. Therefore, CS(u)CS(v). Thus, from the above three cases, S is a locating set.

 ◻

Since the vertex set of G is an external multiplicative distance-locating set, loce(G) exists for every graph G. Since every multiplicative distance-locating set is an external multiplicative distance-locating set and since every external multiplicative distance-locating set is a locating set, we have the following.

Theorem 6. For every connected graph G, loc(G)loce(G). Moreover, if G is a connected graph G of order n2 for which locd(G) exists, then 1loc(G)loce(G)locd(G).

In Theorem 1 the path Pn of order n2 is the only connected graph with locd(G)=1. It is straight forward to show that the path Pn is also the only connected graph of order n with loce(G)=1.

Theorem 7. Let G be a connected graph G of order n2. Then loce(G)=1 if and only if G=Pn.

It is shown that the complete graph Kn of order n2 is the only connected graph of order n with loc(G)=n1, while locd(Kn) does not exist by Corollary 6. Certainly loce(Kn)=n1 for all n2 as well. On the other hand, Kn is not the only connected graph of order n with external multiplicative location number n1.

Theorem 8. If G is an rregular connected graph of order n and diameter 2, then loce(G)=n1.

Proof. Suppose G is an rregular connected graph of order n and diameter 2. Because of Theorem 7, it suffices to show that for each integer k with 2kn2, there is no external multiplicative distance-locating set of G consisting of k vertices. Assume to the contrary, that there is an external multiplicative distance-locating set of order k in G. Let S={w1,w2,,wk} be an external multiplicative distance-locating set for G, where 2kn2. Let V(G)S={v1,v2,,vnk}. For each viV(G)S, where 1ink, let si be the number of vertices of S that are adjacent to vi, and let ti be the number of vertices of S that are not adjacent to vi. Thus, si+ti=k, 0simin{r,k}, and 0timin{n1r,k}, for all i with 1ink. Since diamG=2, dS(vi)=2ti for all i with 1ink. Since S is an external multiplicative distance-locating set for G, all nk numbers dS(vi) are distinct. Therefore, titj. Since si+ti=k, all nk numbers si are distinct and all nk numbers ti are distinct. Let H=V(G)S be the subgraph induced by V(G)S. Then degH(vi)=rsi for all i with 1ink. Since the nk numbers si are distinct, degH(vi) are distinct, 1ink. Therefore, no two vertices of H have the same degree, which is impossible. Hence loce(G)=n1◻

As an immediate consequence of Theorem 8 we obtain the external location number of the Petersen graph.

Corollary 7. The Petersen graph has external location number 9.

Next we determine the external location number of the complete bipartite graphs.

Theorem 9. For integers r,s1 with r+s4,

loce(Kr,s)={r+s2ifrs,r+s1ifr=s.

Proof. Assume that rs. Let V1={u1,u2,,ur} and V2={v1,v2,,vs} be the partite sets of Kr,s. If r=s, then by Theorem 8 loce(Kr,s)=r+s1. So we may assume that r<s. Every external multiplicative distance-locating set of Kr,s contains at least r1 vertices from V1 and at least s1 vertices from V2. Thus, loce(Kr,s)r+s2. Let W=(V1{ur})(V2{vs}). Then dW(ur)=2(r1) and dW(vs)=2(s1). Suppose dW(ur)=dW(vs). Then r=s, which is a contradiction. Therefore, dW(ur)dW(vs). Thus, W is an external multiplicative distance-locating set for Kr,s. Since loce(Kr,s)r+s2, W is the minimum external multiplicative distance-locating set for Kr,s. Therefore, loce(Kr,s)=r+s2◻

4. The Magic Location Number of a graph

Let G be a connected graph with vertex set V(G). Let S be a subset of V(G). We define the distance of a vertex v with respect to S by dS(v)=xS,xvd(v,x). If dS(u)=dS(v) for each pair u,v of distinct vertices of GS, then S is called a magic locating set of G. The cardinality of a minimum magic locating set of G is called the magic location number of G. It is denoted by locM(G). Every distance-locating set is not a magic locating set and every external distance-locating set is not a magic locating set.

The following Theorem 10 characterizes graph G with locM(G)=1.

Theorem 10. Let G be a connected graph of order n2. Then locM(G)=1 if and only if G contains a vertex of degree n1.

Proof. Suppose locM(G)=1. Let S={w} be a minimum magic locating set for G. Then d(u,w)=d(v,w) for each pair u,v of distinct vertices of V(G)S. Assume that d(u,w)=l>1 for some uV(G)S, where 2ln1. Then there exists a path P:u=u0,u1,u2,,ul1,ul=w in G. Therefore, d(u,w)=l and d(ul1,w)=1, which is a contradiction. Thus, d(u,w)=1 for all uV(G)S. Hence, w is adjacent to all the vertices of GS. Therefore, deg(w)=n1.

Conversely, assume that G contains a vertex of degree n1. Let w be a vertex of G such that deg(w)=n1. Let S={w}. Then dS(u)=1 for all uV(G)S. Therefore, S is a minimum magic locating set for G. Hence, locM(G)=1◻

Corollary 8. The magic location number of the graphs Kn,K1,n,Wn,Fn is 1.

In Theorem 11 and Theorem 12 we determine the magic location number of an even cycle and the complete bipartite graphs.

Theorem 11. If Cn is an even cycle, then locM(Cn)=2.

Proof. Let Cn:v1,v2,,vk,,v2k be an even cycle. Let S={vk,v2k} be a subset of V(Cn). Then dS(vi)=k for 1i<k and dS(vi)=k for k<i<2k. Hence S is a magic locating set for Cn. Therefore, locM(Cn)2. By Theorem 10 locM(Cn)=2◻

Theorem 12. For m,n2, locM(Km,n)=2.

Proof. Let G be a complete bipartite graph with vertex set V=V1V2 where V1={v1,v2,,vm} and V2={u1,u2,,un}. Let S={v1,u1} be a subset of V(G). Then dS(vi)=3 for 1im and dS(vi)=3 for 1in. Hence S is a magic locating set for G. Therefore, locM(Km,n)2. By Theorem 10 locM(Km,n)=2◻

Theorem 13 shows that the magic location number of a path Pn of order n2 is less than or equal to n2.

Theorem 13. If Pn is a path on n vertices, then locM(Pn)n2.

Proof. Let Pn:v1,v2,,vk,,vn be a path on n vertices. Let S={v2,v3,,vn1} be a subset of the vertex set of Pn. Then dS(v1)=1+2++(n2)=(n2)(n1)2 and dS(vn)=(n2)+(n3)++2+1=(n2)(n1)2. Thus, S is a magic locating set for Pn. Therefore, locM(Pn)n2◻

5. Conclusion

We have defined some new concepts Multiplicative Distance-locating set, multiplicative distance location number, External Multiplicative location number and magic location number of graphs. We have discussed the existence or non-existence of these numbers for some well known classes of connected graphs. For future study we would like to propose the following open problems.

  1. If G is a connected graph of diameter 3 for which locd(G) exists, then what about G?

  2. For what values of n and m, locd(PnCm)=4.

  3. For what values of n and m, locd(PnCm)=3.

  4. Does equality holds in Theorem 13. Based on our experience we believe that equality holds.

Acknowledgment

The authors would like to thank the two referees for their useful suggestions and comments.

References:

  1. Slater, P. J., 1975. Leaves of trees. Congressus Numerantium, 14, pp.549-559.
  2. Slater, P. J., 1988. Dominating and reference sets in graphs. Journal of Mathematical and Physical Sciences, 22, pp.445-455.
  3. Harary, F. and Melter, R. A., 1976. On the metric dimension of a graph. Ars Combinatoria, 2, pp.191-195.
  4. Chartrand, G., Erwin, D., Slater, P. J. and Zhang, P., 2003. Distance-location number of graphs. Utilitas Mathematica, 63, pp.65-79.