# The Locating Chromatic Number of Book Graph

Authors: Nur Inayah; Wisnu Aribowo; Maiyudi Mariska Windra Yahya
Journal: Journal of Mathematics
 (2021)

---

## Abstract

LetG=VG,EG be a connected graph and c:VG⟶1,2,…,k be a proper k-coloring of G. Let Π be a partition of vertices of G induced by the coloring c. We define the color code cΠv of a vertex v∈VG as an ordered k-tuple that contains the distance between each partition to the vertex v. If distinct vertices have distinct color code, then c is called a locatingk-coloring of G. The locating chromatic number of G is the smallest k such that G has a locating k-coloring. In this paper, we determine the locating chromatic number of book graph.


---

## Body

## 1. Introduction

All graphs considered in this paper are assumed to be simple, connected, and undirected. LetG=VG,EG be a graph with vertex set VG and edge set EG. By Pn and Sn, we denote a path on n vertices and a star on n+1 vertices, respectively. The distance, du,v, between two vertices u and v is defined as the length of the shortest path connecting them in G.For a graphG and a positive integer k, a coloring c:VG⟶1,2,…,k with cu≠cv for every two adjacent vertices u and v is called a proper k-coloring of G. Let Π=C1,C2,…,Ck be a partition of vertices of G induced by the coloring c, where Ci denotes the set of vertices receiving color i. A color code, cΠv, of a vertex v with respect to Π is an ordered k-tuple du,C1,du,C2,…,du,Ck, where du,Ci=mindu,x:x∈Ci for every i=1,2,…,k. If distinct vertices have distinct color codes, then c is called a locating k-coloring of G. The locating chromatic number of G, denoted by χLG, is the smallest k for which G has a locating k-coloring.The concept of locating chromatic number of a graph was introduced in 2002 by Chatrand et al. [1]. This concept is derived from the graph partition dimension and graph coloring. The study about locating chromatic number of a graph has grown constantly. Chartrand et al. [1] determined the locating chromatic number of some well-known graph classes such as paths with χLPn=3 for n≥3, cycles with χLCn=3 for odd n≥3 and χLCn=4 for even n≥4, and double stars with χLSm,n=n+1 for 1≤m≤n and n≥2. In [2], Behtoei and Omoomi investigated the locating chromatic number for Cartesian product of graphs. Welyyanti et al. [3] discussed the locating chromatic number for disconnected graphs. Furthermore, the locating chromatic number of spinner graph was proved by Rianti and Narwen [4].LetG and H be two given graphs. The Cartesian product of G and H, denoted by G×H, is a graph having the vertex set VG×H=VG×VH such that two distinct vertices u1,v1 and u2,v2 are adjacent if and only if u1=u2 and v1v2∈EH or v1=v2 and u1u2∈EG.For a positive integern≥1, a book graph, denoted by Bn, is a graph obtained from n copies of a cycle of order 4 sharing one common edge. The book graph Bn is also called the Cartesian product P2×Sn. In this paper, we investigate the locating chromatic number of book graph.The following theorem proved by Chartrand et al. [1] is useful in determining the locating chromatic number of a graph.Theorem 1.
Letc be a locating coloring in a connected graph G and Nv be the set of vertices adjacent to v. If u and v are distinct vertices of G such that du,w=dv,w for all w∈VG−u,v, then cu≠cv. In particular, if u and v are nonadjacent vertices of G such that Nu=Nv, then cu≠cv.


## 2. Result and Discussion

In this section, we determine the exact value for the locating chromatic number of book graphs. LetBn be a book graph with the vertex set VBn=ui,vi:i=0,1,…,n and the edge set EBn=uivi:i=0,1,…,n∪u0ui,v0vi:i=1,2,…,n.Two observations below follow from definition of proper coloring.Observation 1.
Letc be a locating coloring of the book graph Bn, n≥1. Then, cui≠cvi for i=0,1,…,n.Observation 2.
Letc be a locating coloring of the book graph Bn, n≥1. Then, cu0≠cui and cv0≠cvi for i=1,2,…,n.Lemma 1.
Letc be a locating coloring of the book graph Bn,n≥1. Then, cui,cvi≠cuj,cvj for 1≤i≠j≤n.Proof.
Assume thatcui,cvi=cuj,cvj for some i and j,i≠j. This means that cui=cuj and cvi=cvj. We know that dui,x=duj,x for every x∈VBn−ui,uj,vi,vj. As cvi=cvj and dui,vi=duj,vj=1, regardless the color of x, we have cΠui=cΠuj, a contradiction.Lemma 2.
Letc be a locating k-coloring of the book graph Bn, for k≥4 and n≥1. Then,(1)n≤2k−22+2k−1−1.Proof.
Start coloring the graph by giving colorC1 and C2 for the vertices in the middle, that is, cu0=C1 and cv0=C2. From Observation 2, we know that we should have cui≠C1 and cvi≠C2 for each i=1,2,…,n.Case 1.
Assumecua,cva does not contain either C1 or C2. Thus, the total color that we can choose is k−22×2 because every outer part of sheets requires 2 different colors from observation 1, which means there are k−22possibilities. But, since cua and cva are reversible without any consequences, the total that can be obtained is k−22×2.Case 2.
Ifcua=2, the total possibility of the colors being used is k−1 because cva can only be given with 1,3,4,…,k, where only one color can be used by book graph Bn for n≥2. The illustration is shown in Figure 1.Figure 1
Illustration of Case2.Case 3.
Ifcva=1, the total colors can be used are k−1 because cua can only be given by color 2,3,4,…,k, where only two colors can be used on book graph Bn for n≥2. The illustration is shown in Figure 2.
Since the coloringcva=1 and cua=2 have been used in Case 2, then the coloring is not reusable, and thus, the total coloring is k−1−1. If uses k colors, then χLBn must satisfy the following (2)n≤2k−22+k−1+k−1−1,n≤2k−22+2k−1−1.Figure 2
Illustration of Case3.Theorem 2.
Locating chromatic number of book graphBn is(3)χLBn=mink:n≤2k−22+2k−1−1,for k≥4.Proof.
Firstly, we will prove the existence ofχLBn. We can clearly see that k:n≤2k−22+2k−1−1 is the subset from a set of real numbers. So from the well-ordering principle, the set must have the smallest element, say(4)k∗:=mink:n≤2k−22+2k−1−1,that yields(5)k∗−1≥mink:n≤2k−22+2k−1−1=k∗.
It was contradiction, which means it is impossible that the locating chromatic of book graph has a coloring fork∗−1 colors. It should be(6)χLBn=k∗=mink:n≤2k−22+2k−1−1,fork≥4.Corollary 1.
Locating chromatic number of book graphBn is(7)χLBn=n−34+32.Proof.
Letk be the color needed for locating chromatic of book graph Bn, then(8)n≤2k−22+2k−1−1,n≤k−2k−32×2+2k−2−1,k2−5k+6+2k−3≥n,k2−3k+3≥n,k−322−94+3≥n,k−322+34≥n,k−322≥n−34,k≥n−34+32.
Then, the smallest possiblek is(9)kmin=n−34+32.


## 3. Conclusion

The locating chromatic number of book graph that has been found is(10)χLBn=k∗=mink:n≤k−22+2k−1−1,fork≥4,or(11)kmin=n−34+32.



---

*Source: 3716361-2021-11-24.xml*