# On the Locating Chromatic Number of Certain Barbell Graphs

Authors: Asmiati; I. Ketut Sadha Gunce Yana; Lyra Yulianti
Journal: International Journal of Mathematics and Mathematical Sciences
 (2018)

---

## Abstract

The locating chromatic number of a graphG is defined as the cardinality of a minimum resolving partition of the vertex set V(G) such that all vertices have distinct coordinates with respect to this partition and every two adjacent vertices in G are not contained in the same partition class. In this case, the coordinate of a vertex v in G is expressed in terms of the distances of v to all partition classes. This concept is a special case of the graph partition dimension notion. In this paper we investigate the locating chromatic number for two families of barbell graphs.


---

## Body

## 1. Introduction

The partition dimension was introduced by Chartrand et al. [1] as the development of the concept of metric dimension. The application of metric dimension plays a role in robotic navigation [2], the optimization of threat detecting sensors [3], and chemical data classification [4]. The concept of locating chromatic number is a marriage between the partition dimension and coloring of a graph, first introduced by Chartrand et al in 2002 [5]. The locating chromatic number of a graph is a newly interesting topic to study because there is no general theorem for determining the locating chromatic number of any graph.LetG=(V,E) be a connected graph. We define thedistance as the minimum length of path connecting vertices u and v in G, denoted by d(u,v). A k-coloring of G is a function c:V(G)→{1,2,…,k}, where c(u)≠c(v) for any two adjacent vertices u and v in G. Thus, the coloring c induces a partition Π of V(G) into k color classes (independent sets) C1,C2,…,Ck, where Ci is the set of all vertices colored by the color i for 1≤i≤k. Thecolor codecΠ(v) of a vertex v in G is defined as the k-vector (d(v,C1),d(v,C2),…,d(v,Ck)), where d(v,Ci)=min{d(v,x):x∈Ci} for 1≤i≤k. The k-coloring c of G such that all vertices have different color codes is called alocating coloring of G. Thelocating chromatic number of G, denoted by χL(G), is the minimum k such that G has a locating coloring.The following theorem is a basic theorem proved by Chartrand et al. [5]. The neighborhood of vertex u in a connected graph G, denoted by N(u), is the set of vertices adjacent to u.Theorem 1 (see [5]).
Letc be a locating coloring in a connected graph G. If u and v are distinct vertices of G such that d(u,t)=d(v,t) for all t∈V(G)-{u,v}, then c(u)≠c(v). In particular, if u and v are non-adjacent vertices of G such that N(u)=N(v), then c(u)≠c(v).The following corollary gives the lower bound of the locating chromatic number for every connected graphG.Corollary 2 (see [5]).
IfG is a connected graph and there is a vertex adjacent to k leaves, then χL(G)≥k+1.There are some interesting results related to the determination of the locating chromatic number of some graphs. The results are obtained by focusing on certain families of graphs. Chartrand et al. in [5] have determined all graphs of order n with locating chromatic number n, namely, a complete multipartite graph of n vertices. Moreover, Chartrand et al. [6] have succeeded in constructing tree on n vertices, n≥5, with locating chromatic numbers varying from 3 to n, except for (n-1). Then Behtoei and Omoomi [7] have obtained the locating chromatic number of the Kneser graphs. Recently, Asmiati et al. [8] obtained the locating chromatic number of the generalized Petersen graph P(n,1) for n≥3. Baskoro and Asmiati [9] have characterized all trees with locating chromatic number 3. In [10] all trees of order n with locating chromatic number n-1 were characterized, for any integers n and t, where n>t+3 and 2≤t<n/2. Asmiati et al. in [11] have succeeded in determining the locating chromatic number of homogeneous amalgamation of stars and their monotonicity properties and in [12] for firecracker graphs. Next, Wellyyanti et al. [13] determined the locating chromatic number for complete n-ary trees.The generalized Petersen graphP(n,m), n≥3 and 1≤m≤⌊(n-1)/2⌋, consists of an outer n-cycle y1,y2,…,yn, a set of n spokes yixi, 1≤i≤n, and n edges xixi+m, 1≤i≤n, with indices taken modulo n. The generalized Petersen graph was introduced by Watkins in [14]. Let us note that the generalized Petersen graph P(n,1) is a prism defined as Cartesian product of a cycle Cn and a path P2.Next theorems give the locating chromatic numbers for complete graphKn and generalized Petersen graph P(n,1).Theorem 3 (see [6]).
Forn≥2, the locating chromatic number of complete graph Kn is n.Theorem 4 (see [8]).
The locating chromatic number of generalized Petersen graphP(n,1) is 4 for odd n≥3 or 5 for even n≥4.Thebarbell graph is constructed by connecting two arbitrary connected graphs G and H by a bridge. In this paper, firstly we discuss the locating chromatic number for barbell graph Bm,n for m,n≥3, where G and H are complete graphs on m and n vertices, respectively. Secondly, we determine the locating chromatic number of barbell graph BP(n,1) for n≥3, where G and H are two isomorphic copies of the generalized Petersen graph P(n,1).


## 2. Results and Discussion

Next theorem proves the exact value of the locating chromatic number for barbell graphBn,n.Theorem 5.
LetBn,n be a barbell graph for n≥3. Then the locating chromatic number of Bn,n is χL(Bn,n)=n+1.Proof.
LetBn,n, n≥3, be the barbell graph with the vertex set V(Bn,n) = {ui,vi:1≤i≤n} and the edge set E(Bn,n) = ⋃i=1n-1uiui+j:1≤j≤n-i ∪ ⋃i=1n-1vivi+j:1≤j≤n-i ∪ {unvn}.
First, we determine the lower bound of the locating chromatic number for barbell graphBn,n for n≥3. Since the barbell graph Bn,n contains two isomorphic copies of a complete graph Kn, then with respect to Theorem 3 we have χL(Bn,n)≥n. Next, suppose that c is a locating coloring using n colors. It is easy to see that the barbell graph Bn,n contains two vertices with the same color codes, which is a contradiction. Thus, we have that χL(Bn,n)≥n+1.
To show thatn+1 is an upper bound for the locating chromatic number of barbell graph Bn,n it suffices to prove the existence of an optimal locating coloring c:V(Bn,n)→{1,2,…,n+1}. For n≥3 we construct the function c in the following way: (1)cui=i,1≤i≤ncvi=n,fori=1i,for2≤i≤n-1n+1,otherwise.By using the coloring c, we obtain the color codes of V(Bn,n) as follows: (2)cΠui=0,forithcomponent,1≤i≤n2,forn+1thcomponent,1≤i≤n-11,otherwise,cΠvi=0,forithcomponent,2≤i≤n-1fornthcomponent,i=1,andforn+1thcomponent,i=n,3,for1stcomponent,1≤i≤n-12,for1stcomponent,i=n1,otherwise.Since all vertices in V(Bn,n) have distinct color codes, then the coloring c is desired locating coloring. Thus, χL(Bn,n)=n+1.Corollary 6.
Forn,m≥3, and m≠n, the locating chromatic number of barbell graph Bm,n is (3)χLBm,n=max⁡m,n.Next theorem provides the exact value of the locating chromatic number for barbell graphBP(n,1).Theorem 7.
LetBP(n,1) be a barbell graph for n≥3. Then the locating chromatic number of BP(n,1) is (4)χLBPn,1=4,for  oddn5,for  evenn.Proof.
LetBP(n,1), n≥3, be the barbell graph with the vertex set V(BP(n,1))={ui,un+i,wi,wn+i:1≤i≤n} and the edge set E(BP(n,1)) = ​uiui+1,un+iun+i+1,wiwi+1, wn+iwn+i+1:1≤i≤n-1​ ∪ {unu1,u2nun+1,wnw1,w2nwn+1} ∪ {uiun+i,wiwn+i:1≤i≤n} ∪ {unwn}.
Let us distinguish two cases.
Case 1 (n odd). According to Theorem 4 for n odd we have χL(BP(n,1))≥4. To show that 4 is an upper bound for the locating chromatic number of the barbell graph BP(n,1) we describe an locating coloring c using 4 colors as follows: (5)cui=1,fori=13,for  eveni,i≥24,for  oddi,i≥3.cun+i=2,fori=13,for  oddi,i≥34,for  eveni,i≥2.cwi=1,for  oddi,i≤n-22,for  eveni,i≤n-13,fori=n.cwn+i=1,for  eveni,i≤n-12,for  oddi,i≤n-24,fori=n.For n odd the color codes of V(BP(n,1)) are(6)cΠui=i,for2ndcomponent,i≤n+12i-1,for1stcomponent,i≤n+12n-i+1,for1stcomponent,i>n+12n-i+2,for2ndcomponent,i>n+120,for3thcomponent,ieven,i≥2for4thcomponent,iodd,i≥31,otherwise.cΠun+i=i,for1stcomponent,i≤n+12i-1,for2ndcomponent,i≤n+12n-i+1,for2ndcomponent,i>n+12n-i+2,for1stcomponent,i>n+120,for4thcomponent,ieven,i≥2for3thcomponent,iodd,i≥31,otherwise.cΠwi=i,for3thcomponent,i≤n-12i+1,for4thcomponent,i≤n-12n-i,for3thcomponent,i≥n+12n-i+1,for4thcomponent,i≥n+120,for2ndcomponent,ieven,i≤n-1for1stcomponent,iodd,i≤n-21,otherwise.cΠwn+i=i,for4thcomponent,i≤n-12i+1,for3thcomponent,i≤n-12n-i,for4thcomponent,i≥n+12n-i+1,for3thcomponent,i≥n+120,for1stcomponent,ieven,i≤n-1for2ndcomponent,iodd,i≤n-21,otherwise.Since all vertices in BP(n,1) have distinct color codes, then the coloring c with 4 colors is an optimal locating coloring and it proves that χL(BP(n,1))≤4.
Case 2 (n even). In view of the lower bound from Theorem 7 it suffices to prove the existence of a locating coloring c:V(BP(n,1))→{1,2,…,5} such that all vertices in BP(n,1) have distinct color codes. For n even, n≥4, we describe the locating coloring in the following way: (7)cui=1,fori=13,for  eveni,2≤i≤n-24,for  oddi,3≤i≤n-15,fori=n.cun+i=2,fori=13,for  oddi,i≥34,for  eveni,i≥2.cwi=1,for  oddi,i≤n-32,for  eveni,i≤n-23,fori=n-14,fori=n.cwn+i=1,for  eveni,i≤n-22,for  oddi,i≤n-15,fori=n.In fact, our locating coloring of BP(n,1), n even, has been chosen in such a way that the color codes are(8)cΠui=i,for2ndand5thcomponents,i≤n2i-1,for1stcomponent,i≤n2n-i,for5thcomponent,i>n2n-i+1,for1stcomponent,i>n2n-i+2,for2ndcomponent,i>n20,for3thcomponent,ieven,2≤i≤n-2for4thcomponent,iodd,3≤i≤n-12,for4thcomponent,i=1for3thcomponent,i=n1,otherwise.cΠun+i=i,for1stcomponent,i≤n2i-1,for2ndcomponent,i≤n2n+i,for5thcomponent,i≤n2n-i+1,for2ndand5thcomponents,i>n2n-i+2,for1thcomponent,i>n20,for3thcomponent,iodd,3≤i≤n-1for4thcomponent,ieven,2≤i≤n2,for3thcomponent,i=11,otherwise.cΠwi=i,for4thcomponent,i≤n2i+1,for5thcomponent,i≤n2for3thcomponent,i≤n2-1n-i,for4thcomponent,i>n2n-i+1,for5thcomponent,i>n2n-i-1,for3thcomponent,n2≤i≤n-10,for1stcomponent,iodd,i≤n-3for2ndcomponent,ieven,i≤n-22,for1stcomponent,i=n-1for2ndcomponent,i=n1,otherwise.cΠwn+i=i,for5thcomponent,i≤n2i+1,for4thcomponent,i≤n2i+2for3thcomponent,i≤n2-1n-i,for3thcomponent,n2≤i≤n-1for5thcomponent,i>n2n-i+1,for4thcomponent,i>n20,for1stcomponent,ieven,i≤n-2for2ndcomponent,iodd,i≤n-12,for1stand3thcomponents,i=n1,otherwise.Since for n even all vertices of BP(n,1) have distinct color codes then our locating coloring has the required properties and χL(BP(n,1))≤5. This concludes the proof.



---

*Source: 5327504-2018-08-05.xml*