Menu
Let \(c\) be a proper \(k\)-coloring of a connected graph \(G\) and \(\pi=\{S_{1},S_{2},\ldots,S_{k}\}\) be an ordered partition of the vertex set \(V(G)\) into the resulting color classes, where \(S_{i}\) is the set of all vertices that receive the color \(i\). For a vertex \(v\) of \(G\), the color code \(c_{\pi}(v)\) of \(v\) with respect to \(\pi\) is the ordered \(k\)-tuple \(c_{\pi}(v)=(d(v,S_{1}),d(v,S_{2}),\ldots,d(v,S_{k}))\), where \(d(v,S_{i})=min\{d(v,u):\textit{ } u\in S_{i}\}\) for \(1\leqslant i \leqslant k\). If all distinct vertices of \(G\) have different color codes, then \(c\) is called a locating coloring of \(G\). The locating chromatic number is the minimum number of colors needed in a locating coloring. In this paper, we determine the locating-chromatic number for the middle graphs of Path, Cycle, Wheel, Star, Gear and Helm graphs.
Let \(G\) be a connected graph
without loops and multiple edges with vertex set \(V(G)\) and edge set \(E(G)\). The middle
graph \(M(G)\) of the graph
\(G\) is defined by the vertex set
\(V(G)\cup E(G)\), where two vertices
are adjacent if and only if they are either adjacent edges of \(G\) or one is a vertex and the other is an
edge incident with it. Note that every middle graph is a subdivision
graph, however not every subdivision graph is a middle graph. Many
theoretical graph properties and invariants of a middle graph were
studied in the literature see [1] and [2]. For a connected graph \(G\), the distance
between the vertices \(u\) and \(v\) in \(V(G)\), denoted by \(d(u,v)\), is the length of the shortest
path between them, whereas for a subset \(S\) of \(V(G)\), the distance between \(u\) and \(S\) is given by
\(d(u,S)=min\{d(u,x):~ x\in S\}\). The
neighborhood of a vertex \(u\) in a graph \(G\), \(N(u)\), is the set of all vertices adjacent
to \(u\), i.e. \(N(u)=\{u\in V(G):~ uv\in E(G)\}\).
Moreover, the degree of a vertex \(u\), \(deg_{G}(u)\), is defined as the cardinality
of \(N(u)\).
A proper \(k\)-coloring of \(G\), \(k\in \mathbb{N}\), is a function \(c\) defined from \(V(G)\) onto a set of colors \([k]=\{1,2,\ldots,k\}\) such that every two adjacent vertices of \(G\) have different colors. Thus, the coloring \(c\) can be considered as a partition of \(V(G)\) into color classes \(S_{1},S_{2},\ldots,S_{k}\), where the vertices of \(S_{i}\) are colored by the color \(i\) such that no two vertices belonging to \(S_{i}\) are adjacent for \(1\leq i\leq k\). The minimum \(k\) for which \(G\) has a proper \(k\)-coloring is the chromatic number of \(G\), denoted by \(\chi( G)\). Let \(\pi=\{S_{1},S_{2},\ldots,S_{k}\}\) be a partition of \(V(G)\) induced by \(c\), the color code \(c_{\pi }(v)\) of a vertex \(v\) in \(V(G)\) with respect to \(\pi\) is defined as the ordered \(k\)-tuple \(c_{\pi}( v) =( d( v,S_{1}) ,d( v,S_{2}),\ldots,d( v,S_{k}))\). If all the distinct vertices of \(G\) have distinct color codes, then \(c\) is called a locating \(k\)-coloring of \(G\). The minimum \(k\) for which there exists a locating coloring of \(G\) using exactly \(k\) colors is the locating chromatic number of \(G\), denoted by \(\chi _{L}(G)\). Since every locating coloring is a proper coloring, \(\chi(G) \leqslant \chi _{L}(G)\). The locating-chromatic number of a graph is a combination concept between the partition dimension of a graph and the coloring of a graph. There exist many applications of graph coloring and labeling in various fields. These notions play an important role and they are related to different applications such as computer science and communication network (see [3] and [4]).
The concept of locating coloring of graphs was first introduced by Chartrand et al. [5] in \(2002\). They established some bounds for the locating chromatic number of a connected graph. They proved that for a connected graph \(G\) with \(n\geqslant 3\), \(\chi _{L}(G) =n\) if and only if \(G\) is a complete multi-partite graph. Also for paths and cycles of order \(n\geqslant 3\), they demonstrated that \(\chi _{L}( P_{n}) =3\), \(\chi _{L}( C_{n})=3\) when \(n\) is odd, and \(\chi _{L}( C_{n}) =4\) when \(n\) is even. The authors in [6] characterized all graphs of order \(n\) with locating-chromatic number \(n-1\). Many results of the locating chromatic graph for connected graph were studied. Asmiati et al. in [7] and [8] determined the locating-chromatic number of special classes of trees, an amalgamation of stars and a firecracker graph. Behtoe and Omoomi in [9] found the locating-chromatic numbers of the Kneser graph. In [10] all graphs containing cycles with locating-chromatic number \(3\) are characterized.
The locating-chromatic numbers of graphs obtained by some graph operations are also worthy studying. Baskoro and Purwasih in [11] studied the locating-chromatic number for the corona product of graphs. Behtoei et al. [12], on the other hand, gave the locating-chromatic number for the Cartesian product of any two graphs. In [13] the locating-chromatic number of the fan graph, wheel and friendship graph for join multiplication of two graphs are determined.
Recently, Ghanem et al. [14] figured out the locating chromatic number of powers of paths and powers of cycles. In this paper, we determine the locating-chromatic number for the middle graphs of Path, Cycle, Star, Wheel, Gear and Helm graphs.
Let \(V(P_{n})=\left\{ x_{1},x_{2},x_{3},\ldots,x_{n}\right\}\) and \(E(P_{n}) =\left\{x_{i}x_{i+1}: 1\leqslant i \leqslant n-1 \right\}\). The middle graph of the n-path \(P_{n}\) is given by subdividing each edge exactly once and joining all the middle vertices of adjacent edges of \(P_{n}\). Denote the middle vertex of the edge \(x_{i}x_{i+1}\) by \(y_{i}\) where \(1\leqslant i \leqslant n-1\). In this section, we determine the locating chromatic number of a middle graph of \(P_{n}\).
Theorem 1. For any postive integer \(n> 3\), \(\chi _{L}(M(P_{n}))=4.\)
Proof. Since \(M(P_{n})\) contains \(3\)-clique, \(3\leqslant\chi(M(P_{n}))\leqslant \chi_{L}(M(P_{n}))\). Let \(c\) be locating \(3\)-coloring of \(M(P_{n})\). Observe that \(M(P_{n})\) contains at least two distinct \(3\)-cliques, so definitely two vertices of \(M(P_{n})\) must have the same color, as well as the same color code. Thus, \(\chi_{L}(M(P_{n}))\geqslant 4\).
Define the coloring function \(c:V(M(P_{n}))\longrightarrow \{1,2,3,4\}\) as follows: \[c(x_{i})=\left\{ \begin{array}{l} 1\qquad \text{if} \qquad i=1, \\ 2 \qquad \text{if} \qquad i\equiv 0\pmod 3 \qquad \text{and} \qquad 1\leqslant i\leqslant n, \\ 3\qquad \text{if} \qquad i\equiv 2\pmod 3 \qquad \text{and} \qquad 1\leqslant i\leqslant n, \\ 4\qquad \text{if} \qquad i\equiv 1\pmod 3 \qquad \text{and} \qquad 2\leqslant i\leqslant n. \end{array} \right.\] \[c(y_{i})=\left\{ \begin{array}{l} 2\qquad \text{if} \qquad i\equiv 1\pmod 3 \qquad \text{and} \qquad 1\leqslant i\leqslant n, \\ 3\qquad \text{if} \qquad i\equiv 0\pmod 3 \qquad \text{and} \qquad 1\leqslant i\leqslant n, \\ 4\qquad \text{if} \qquad i\equiv 2\pmod 3 \qquad \text{and} \qquad 1\leqslant i\leqslant n. \end{array} \right.\]
Hence, we obtain a partition \(\pi =\left\{S_{1},S_{2},S_{3},S_{4}\right\}\) of \(V(M(P_{n}))\), where \(S_{1}=\{ x_{1}\}\), \(S_{2}=\{x_{3},x_{6},\ldots\}\cup\{y_{1},y_{4},\ldots\}\), \(S_{3}=\{x_{2},x_{5},\ldots\}\cup\{y_{3},y_{6},\ldots\}\), and \(S_{4}=\{x_{4},x_{7},\ldots\}\cup \{y_{2},y_{5},\ldots\}\).
Now, observe that for a distinct pair \(u,v\) of \(V(M(P_{n}))\), we have \(d(u,x_{1})=d(v,x_{1})\) if and only if \(\{u,v\}=\{x_{i},y_{i}\}\) for some \(i\in \{2,\ldots,n-1\}\). Since \(x_{i}\) and \(y_{i}\) belong to different color classes, it follows that \(d(u,S_{1})\neq d(v,S_{1})\) as long as \(u\) and \(v\) belong to the same color class. As a result, this coloring \(c\) is indeed a locating \(4\)-coloring of \(M(P_{n})\). ◻
Let \(V(C_{n})=\{ x_{1},x_{2},x_{3},\ldots,x_{n}\}\) and \(E(C_{n}) =\{x_{i}x_{i+1}: 1\leqslant i \leqslant n-1 \}\cup \{ x_{n}x_{1}\}\). The middle graph of the \(n\)-cycle \(C_{n}\) is given by subdividing each edge exactly once and joining all the middle vertices of the adjacent edges of \(C_{n}\). Denote the middle vertex of the edge \(x_{i}x_{i+1}\) by \(y_{i}\) where \(1\leqslant i \leqslant n-1\) and the middle vertex of the edge \(x_{n}x_{1}\) by \(y_{n}\).
For proof, we rename the vertices as follows:
Let \(V\left( M(C_{n})\right) =\left\{ x_{1},x_{2},x_{3},\ldots,x_{2n}\right\}\) and \(E\left( M(C_{n})\right) =\left\{x_{1}x_{2},x_{2}x_{3},x_{3}x_{4},\ldots,x_{2n-1}x_{2n}\right\} \cup \left\{x_{i}x_{i+2}:\text{ }i=2m\text{ and }1\leqslant m\leqslant n-1\right\} \cup\left\{ x_{2n}x_{2}\right\}\).
In this section, we determine the locating chromatic number of a middle graph of \(C_{n}\).
Theorem 2. For any positive integer \(n\geqslant 3\), \(\chi _{L}(M(C_{n}))\geqslant 4.\)
Proof. Since the graph \(M(C_{n})\) contains a \(3\)-clique, \(\chi_{L}(M(C_{n}))\geqslant 3.\) Assume that \(\chi _{L}(M(C_{n}))=3,\) and \(c\) is a locating coloring of \(M(C_{n})\). Let \(x\) and \(y\) be two distinct vertices of \(M(C_{n})\) such that \(c\left( x\right) =c\left( y\right)\), then they are contained in two distinct \(3\)-cliques and so \(c_{\pi }( x)=c_{\pi }( y)\), a contradiction. ◻
Theorem 3. For \(3\leqslant n\leqslant 8\), \(\chi _{L}(M(C_{n}))=4\).
Proof. If \(n=3,\) let \(S_{1}=\{ x_{3},x_{6}\} ,\) \(S_{2}=\{x_{1},x_{4}\} ,\) \(S_{3}=\{ x_{2}\}\) and \(S_{4}=\left\{x_{5}\right\}\). If \(n=4,\) let \(S_{1}=\left\{ x_{3},x_{8}\right\} ,\) \(S_{2}=\left\{x_{1},x_{4}\right\} ,\) \(S_{3}=\left\{ x_{2},x_{6}\right\}\) and \(S_{4}=\left\{x_{5},x_{7}\right\}\). If \(n=5,\) let \(S_{1}=\left\{ x_{3},x_{6},x_{10}\right\} ,\) \(S_{2}=\left\{x_{1},x_{4},x_{7}\right\} ,\) \(S_{3}=\left\{ x_{2},x_{9}\right\}\) and \(S_{4}=\left\{ x_{5},x_{8}\right\}\). If \(n=6,\) let \(S_{1}=\left\{ x_{3},x_{6},x_{12}\right\} ,\) \(S_{2}=\left\{x_{1},x_{4},x_{7},x_{9}\right\} ,\) \(S_{3}=\left\{ x_{2},x_{10}\right\}\) and \(S_{4}=\left\{ x_{5},x_{8},x_{11}\right\}\). If \(n=7,\) let \(S_{1}=\left\{ x_{3},x_{6},x_{14}\right\} ,\) \(S_{2}=\left\{x_{1},x_{4},x_{7},x_{10}\right\} ,\) \(S_{3}=\left\{x_{2},x_{9},x_{12}\right\}\) and \(S_{4}=\left\{x_{5},x_{8},x_{11},x_{13}\right\}\). If \(n=8,\) let \(S_{1}=\left\{ x_{3},x_{6},x_{13},x_{16}\right\} ,\) \(S_{2}=\left\{ x_{1},x_{4},x_{7},x_{10}\right\} ,\) \(S_{3}=\left\{x_{2},x_{9},x_{12},x_{15}\right\}\), and \(S_{4}=\left\{x_{5},x_{8},x_{11},x_{14}\right\}\). Clearly \(\pi =\left\{ S_{1},S_{2},S_{3},S_{4}\right\}\) is a partition of \(V( M(C_{n}))\), where \(3\leqslant n\leqslant 8\). Therefore, the coloring \(c\) defined by \(c:V( M(C_{n})) \rightarrow \{ 1,2,3,4\}\), where \(c(x_{i})=j\) for any \(x_{i}\in S_{j}\) is a locating \(4\)-coloring for \(M(C_{n})\). ◻
Lemma 1. For \(n\geqslant 9\), let \(c\) be a locating \(4\)-coloring of \(M(C_{n})\) and \(S_{j},1\leqslant j\leqslant 4\) be the color classes of this locating coloring. Let \(M(C_{n})[ R]\) be the induced subgraph of \(M(C_{n})\) by \(R\), where \(R=\{ x_{s},x_{s+1},\ldots,x_{t-1},x_{t} \}\) such that \(x_{s},x_{t}\) belong to \(S_{j}\) and \(R\cap S_{j}=\{x_{s},x_{t}\}\). Then we have the following:
For every \(S_{j}\), there are at most three vertices say \(u_{1},u_{2},u_{3}\in V\left( M(C_{n})\right) \diagdown S_{j}\) such that \(d_{M(C_{n})}\left( u_{i},S_{j}\right) =2\) where \(1\leqslant j\leqslant 4\) and \(1\leqslant i\leqslant 3\).
In \(M(C_{n})\left[ R\right]\), there exist at most three vertices say \(v_{1},v_{2},v_{3}\in V( M(C_{n}[ R] ))\) such that \(d_{M(C_{n})[ R] }( v_{i},\{x_{t},x_{s}\}) =2\).
\(\left\vert S_{j}\right\vert \geqslant 2\), for all \(1\leqslant j\leqslant 4\).
If \(x\notin S_{j}\), then \(d_{M(C_{n})}(x,S_{j})\leqslant 2\).
Proof.
Let \(S_{i}\) be the set of vertices that received the color \(i\), \(1\leqslant i\leqslant 4\) . Assume that there exist four vertices say \(u_{j}\notin S_{i}\) such that \(d_{M(C_{n})}(u_{j},S_{i}) =2\), \(1\leqslant j\leqslant 4\) and \(i\neq j\). Then two vertices of \(M(C_{n})\) say \(u,v\) must be share the same color but each vertex of \(M(C_{n})\) is contained in a 3-clique. Consequently, \(c_{\pi}(u)=c_{\pi}(v)\), contradiction.
Note that for any vertex \(x_{i}\) in \(M(C_{n})[ R]\), such that \(d_{M(C_{n})[R] }( x_{i},\{x_{s},x_{t}\})=2\), we have \(d_{M(C_{n})[ R] }( x_{i},S_{j}) =1\) or \(0\) given that \(x_{s},x_{t}\notin S_{j}\). Then the color code of \(x_{i}\) in \(M(C_{n})[ R]\) is the same in \(M(C_{n})\) and so by the same argument of the proof of part \(1\) we get the result.
Assume that for \(j=1\), \(\left\vert S_{j}\right\vert =1\), say that \(S_{1}=\{ x_{1}\}\), then the distance between each vertex of \(\{x_{3},x_{4},x_{2n-2},x_{2n-1}\}\) and \(S_{1}\) is two, which contradict the part \(1\).
Assume that there exists \(x_{l}\in S_{i}\) such that \(d_{M(C_{n})}(x_{l},S_{j})\geqslant 3\) for some \(j\neq i\). Choose \(x_{s},x_{t}\) such that \(s<t\) and \(x_{s}\) and \(x_{t}\) are the closest vertices in \(S_{j}\) to \(x_{l}\). Then \(s<l<t\) and \(d_{M(C_{n})}(x_{s},x_{l})\geqslant 3\) and\(\ d_{M(C_{n})}(x_{l},x_{t})\geqslant 3\). If \(d_{M(C_{n})}(x_{s},x_{l})=3\) and \(\ d_{M(C_{n})}(x_{l},x_{t})=3\), then \(d_{M(C_{n})[ R]}(x_{l},S_{j})=3\) where \(R=\{x_{s},,\ldots,x_{l},\ldots,x_{t-1},x_{t}\}\). Therefore, \(d_{M(C_{n})[R] }\left( x_{k},S_{i}\right) =2\) whenever \(k\in \left\{ s+1,s+2,t-1,t-2\right\}\). By part \(2\), we get a contradiction. Hence \(d_{M(C_{n})\left[ R\right] }(x_{l},S_{j})\leqslant 2\) and so, \(d_{M(C_{n})}(x_{l},S_{j})\leqslant 2\).
◻
Theorem 4. For \(n\geqslant 9\), \(\chi _{L}(M(C_{n}))=5\).
Proof. Assume that \(\chi _{L}(M(C_{n}))=4\). Let \(c\) be a locating coloring and \(\{S_{i}\), \(1\leqslant i\leqslant 4\}\) be the set of the color classes, say that \(S_{1}\) is of minimum cardinality. Now, let \(S=V\left(M(C_{n})\right) \diagdown S_{1}\), by part \(1\) of Lemma 1 there exist \(m\) vertices in \(S\) where \(m\leqslant 3\) such that the distance between each one of them and \(S_{1}\) is two. So there exist \(\left\vert S\right\vert -m\) vertecies such that \(d_{M(C_{n})}(x_{i},S_{1})=1,\) \(1\leqslant i\leqslant 2n\). If \(u\in S_{2}\), then by part \(4\) of Lemma 1, \(d_{M(C_{n})}(u,S_{j})\leqslant 2\) for \(j=3,4\). Hence \(c_{\pi }\left( u\right) =\left( 1,0,k,d\right)\), where \(k,d\in \left\{1,2\right\}\). But \(u\) is contained in a \(3\)-clique, so \(c_{\pi }(u)\) have three possibilities, similarly for \(S_{3}\) and \(S_{4}\). Thus there are at most \(9\) vertices such that the distance between each one of them and \(S_{1}\) equal to one. Hence \[\left\vert S\right\vert -3\leqslant \left\vert S\right\vert -m\leqslant 9 \\ \Leftrightarrow \left\vert S\right\vert \leqslant 12 \\ \Leftrightarrow 2n-\left\vert S_{1}\right\vert \leqslant 12,\] where \(4\left\vert S_{1}\right\vert \leqslant 2n\). So \(n\leqslant 8\), contradiction. Hence \(\chi _{L}(M(C_{n}))\geqslant 5\), for all \(n\geqslant 9\). Now, define the coloring function \(c:V\left( M(C_{n})\right) \longrightarrow \left\{ 1,2,3,4,5\right\}\) as follows:
If \(n\equiv 0\pmod 4\), then \[c(x_{i})=\left\{\begin{array}{l} 1,~\text{if } ~ i=2n, \\ 2,~ \text{if } ~ i\equiv 1\pmod 4 \text{ and } i\leqslant n+1\text{ or }i\equiv 0\pmod 4 \text{ and } n+1<i<2n, \\ 3,~ \text{if } ~ i\equiv 2\pmod 4 \text{ and }i<n\text{ or }i\equiv 1\pmod 4 \text{ and }n<i<2n, \\ 4,~ \text{if } ~ i\equiv 3\pmod 4 \text{ and }i<n\text{ or }i\equiv 2\pmod 4 \text{ and }n<i<2n, \\ 5,~ \text{if } ~ i\equiv 0\pmod 4 \text{ and } i\leqslant n\text{ or }i\equiv 3\pmod 4 \text{ and }n<i<2n. \end{array} \right.\]
If \(n\equiv 1\pmod 4\), then \[c(x_{i})=\left\{ \begin{array}{l} 1,~ \text{if }~ i=2n, \\ 2,~ \text{if } ~ i\equiv 1\pmod 4 \text{ and }i<n\text{ or }i\equiv 2\pmod 4 \text{ and }n<i<2n, \\ 3,~ \text{if } ~ i\equiv 2\pmod 4 \text{ and }i<n,\text{ }i=n\text{ or }i\equiv 3\pmod 4 \text{ and }n<i<2n, \\ 4,~ \text{if }~ i=3\pmod 4 \text{ and }i<n \text{ or }i\equiv 0\pmod 4 \text{ and }n<i<2n, \\ 5,~ \text{if }~ i\equiv 0\pmod 4 \text{ and }i<n \text{ or }i\equiv 1\pmod 4 \text{ and }n<i<2n. \end{array} \right.\]
If \(n\equiv 2\pmod 4\), then \[c(x_{i})=\left\{ \begin{array}{l} 1,~ \text{if }~ i=2n,\\ 2,~ \text{if }~ i\equiv 1\pmod 4 \text{ and }i<n\text{ or }i\equiv 0\pmod 4 \text{ and }n<i<2n, \\ 3,~ \text{if }~ i\equiv 2\pmod 4 \text{ and } i\leqslant n\text{ or }i\equiv 1\pmod 4 \text{ and }n<i<2n,\\ 4,~\text{if } ~ i\equiv 3\pmod 4 \text{ and }i\leqslant n+1\text{ or }i\equiv 2\pmod 4\text{ and }n+1<i<2n, \\ 5,~ \text{if } ~ i\equiv 0\pmod 4 \text{ and }i<n\text{ or }i\equiv 3\pmod 4 \text{ and }n<i<2n. \end{array} \right.\]
If \(n\equiv 3\pmod 4\), then \[c(x_{i})=\left\{ \begin{array}{l} 1,~ \text{if } ~ i=2n, \\ 2,~ \text{if } ~i\equiv 1\pmod 4 \text{ and }i<n\text{ or }i\equiv 2\pmod 4 \text{ and }n<i<2n, \\ 3,~ \text{if }~ i\equiv 2\pmod 4 \text{ and }i<n\text{ or }i\equiv 3\pmod 4 \text{ and }n<i<2n, \\ 4,~ \text{if }~ i\equiv 3\pmod 4 \text{ and\ }i<n \text{ or }i\equiv 0\pmod 4 \text{ and }n<i<2n, \\ 5,~ \text{if }~i\equiv 0\pmod 4 \text{ and }i<n, \text{ }i=n\text{ or }i\equiv 1\pmod 4 \text{ and }n<i<2n. \end{array} \right.\]
In all the above four cases \(\pi =\left\{ S_{1},S_{2},S_{3},S_{4},S_{5}\right\}\) is a partition of \(V\left( M(C_{n})\right)\) and for any two distinct vertices \(u_{i}\) and \(u_{j}\) in \(S_{l}\) with \(2\leqslant l\leqslant 5\), \(d\left( u_{i},S_{1}\right) \neq d\left( u_{j},S_{1}\right)\), hence \(c_{\pi}\left( u_{i}\right) \neq c_{\pi }\left( u_{j}\right)\). Therefore, all vertices in \(M(C_{n})\) have distinct color codes. ◻
Let \(V\left( K_{1,n}\right) =\left\{x_{0},x_{1},x_{2},x_{3},\ldots,x_{n}\right\}\) and \(E\left( K_{1,n}\right)=\left\{ x_{0}x_{1},x_{0}x_{2},x_{0}x_{3},x_{0}x_{4},\ldots,x_{0}x_{n}\right\}\), then \(K_{1,n}\) is called the \(n\)-star graph. The middle graph of the \(n\)-star graph is given by subdividing each edge exactly once and joining all the middle vertices of adjacent edges of \(K_{1,n}\). Denote the middle vertex corresponding to the edge \(x_{0}x_{i}\) by \(y_{i}\) where \(1\leqslant i\leqslant n\). In this section, we determine the locating chromatic number of a middle graph of a star graph.
Theorem 5. For any positive integer \(n\geqslant 2\), \(\chi _{L}(M(K_{1,n}))=n+1.\)
Proof. The vertices \(x_{0},x_{1},x_{2},x_{3},\ldots,x_{n}\) have distinct colors since they induce an \(n+1\)-clique. Therefore, \(\chi_{L}(M(K_{1,n}))\geqslant n+1.\)
Now, define the coloring function \(c:V\left( M\left( K_{1,n}\right)\right) \longrightarrow \left\{ 1,2,\ldots,n+1\right\}\) in the following way: \[c\left( x_{0}\right) =c\left( x_{i}\right)=n+1,\quad c\left( y_{i}\right) =i ,\quad 1\leqslant i\leqslant n.\] By using the coloring \(c\), we obtain the following color codes of \(V(M(K_{1,n}))\) \[c_{\pi }\left( x_{0}\right) =\left( 1,1,1,\ldots,0\right),\] \[c_{\pi }\left( x_{i}\right) =\left\{ \begin{array}{l} 0 \qquad \text{ for } \left( n+1\right) ^{th}\text{ component,} \\ 1 \qquad \text{ for } i^{th}\text{ component }1\leqslant i\leqslant n, \\ 2 \qquad \text{otherwise.} \end{array} \right.\] \[c_{\pi }\left( y_{j}\right) =\left\{ \begin{array}{l} 0 \qquad \text{ for } j^{th}\text{ component }1\leqslant j\leqslant n, \\ 1 \qquad \text{ otherwise.} \end{array} \right.\] As a result, this coloring \(c\) is indeed a locating \(n+1\)-coloring of \(M(W_{n}).\) ◻
Let \(V\left( W_{n}\right) =\left\{ x_{0},x_{1},x_{2},x_{3},\ldots,x_{n}\right\},\) \(x_{0}\) be the center vertex and other vertices be \(x_{1},x_{2},x_{3},\ldots,x_{n}\) on the rim and \(E( W_{n}) =\{x_{0}x_{i},~ 1\leqslant i\leqslant n\} \cup \{x_{i}x_{i+1},~ 1\leqslant i\leqslant n-1\} \cup \{x_{n}x_{1}\}\). Then \(W_{n}\) is called the \(n\)-wheel graph.
The middle graph of the \(n\)-wheel is given by subdividing each edge only once and joining all the middle vertices of adjacent edges of \(W_{n}\). Denote the middle vertex of the edge \(x_{0}x_{i}\) where \(1\leqslant i\leqslant n\) by \(y_{i}\), the middle vertex of the edge \(x_{i}x_{i+1}\), where \(1\leqslant i\leqslant n-1\) by \(y_{i}^{^{\prime }}\) and the middle vertex of the edge \(x_{n}x_{1}\) by \(y_{n}^{^{\prime }}.\) In this section, we determine the locating chromatic number of the middle graph of \(W_{n}\).
Theorem 6. For \(n=3\), \(\chi _{L}(M(W_{n}))=6.\)
Proof. Let \(c\) be a locating \(4\)-coloring of \(M(W_{3})\). Let \(u\) and \(v\) be two distinct vertices of \(M(W_{3})\) that were assigned the same color by \(c\). Certainly, each one of them is contained in a \(4\)-clique and hence they share the same color code i.e., \(\chi_{L}(M(W_{3}))\geqslant 5\). If \(\chi _{L}(M(W_{3}))=5\), then there exist at least two vertices of \(\{ y_{j},y_{k}^{^{\prime }} :\textbf{ } 1\leqslant j,k\leqslant 3 \}\) that share the same color . So, we get one of the following cases.
Case 1: One repeated color.
Let \(c\left( y_{j}\right) =c\left( y_{k}^{^{\prime }}\right)\). Since \(N\left(y_{j}\right) \cap N\left( y_{k}^{^{\prime }}\right) =\left\{y_{i},1\leqslant i\leqslant 3\right\} \cup \left\{ y_{l}^{^{\prime}},1\leqslant l\leqslant 3\right\} \diagdown \left\{ y_{j},y_{k}^{^{\prime}}\right\}\), we get \(c_{\pi }(y_{j})=c_{\pi }(y_{k}^{^{\prime }}),\) a contradiction.
Case 2: Two repeated colors.
Let \(c\left( y_{1}\right) =c\left(y_{2}^{^{\prime }}\right) =1\), \(c\left( y_{2}\right) =c\left(y_{3}^{^{\prime }}\right) =2\), \(c\left( y_{3}\right) =3\), and \(c\left(y_{1}^{^{\prime}}\right) =4\). Then there is only one vertex of \(\{ x_{0},x_{1},x_{2},x_{3}\}\) that can be colored by the remaining color. Otherwise, \(c_{\pi }(y_{1})=c_{\pi }(y_{2}^{^{\prime }})\) or \(c_{\pi }(y_{2})=c_{\pi }(y_{3}^{^{\prime }})\) which is a contradiction. But on the other hand, if \(c(x_{0}) =5\) or \(c( x_{3}) =5\), then, the vertices \(x_{1},x_{2}\) must share the same color and consequently they have the same color code, which is also a contradiction. On the same vein, we get a contradiction if \(c(x_{1}) =5\) or \(c( x_{2}) =5\).
Case 3: Three repeated colors.
Let \(c( y_{1}) =c\left( y_{2}^{^{\prime }}\right) =1\), \(c\left(y_{2}\right) =c\left( y_{3}^{^{\prime }}\right) =2\), and \(c(y_{3}) =c( y_{1}^{^{\prime }}) =3\). Clearly, \(c( x_{i})\in \{4,5\}\) for \(0\leqslant i\leqslant 3\}\). Consequently, there exist two vertices \(x_{i},x_{j}\) share the same color, but each one of them is contained in a different \(4\)-clique. Moreover, \(d(x_{i},x_{j})=2\), so \(x_{i}\) and \(x_{j}\) must have the same color code, a contradiction.
From the previous cases, we get \(\chi _{L}(M(W_{3}))\geqslant 6\). Let \(S_{1}=\left\{ x_{0}\right\} ,\) \(S_{2}=\left\{ y_{1},x_{2}\right\}\), \(S_{3}=\left\{ y_{2},x_{3}\right\} ,\) \(S_{4}=\left\{ y_{3},y_{1}^{^{\prime}}\right\}\), \(S_{5}=\left\{ y_{3}^{^{\prime }}\right\},\) and \(S_{6}=\left\{x_{1},y_{2}^{^{\prime }}\right\}\), then the coloring \(c\) defined by \(c:V\left( M(W_{3})\right)\longrightarrow \left\{ 1,\ldots,6\right\}\) such that \(c\left( u\right) =j\) for all \(u\in S_{j}\) is a locating \(6\)-coloring of \(M(W_{3})\).
◻
Theorem 7. For \(n=4\), \(\chi _{L}(M(W_{n}))=6\).
Proof. The vertices \(x_{0},y_{1},y_{2},y_{3},y_{4}\) induce a \(5\)-clique, so \(\chi _{L}(M(W_{4}))\geqslant 5.\) Now, suppose that \(\chi _{L}(M(W_{4}))=5\). Let \(c\) be a locating coloring of \(M(W_{4})\), then the neighbors of \(y_{j}^{^{\prime }},\) \(1\leqslant j\leqslant 4\), are colored by three or four colors since each \(y_{j}^{^{\prime }}\) is a common vertex between two \(4\)-cliques. If there is \(y_{j}^{^{\prime }}\) such that its neighbor colors set is \(\{1,2,3,4,5\} \setminus \{c(y_{j}^{^{\prime }})\}\), then \(c_{\pi }( y_{j}^{^{\prime}}) =c_{\pi }( y_{i})\) or \(c_{\pi }( y_{j}^{^{\prime}}) =c_{\pi }( x_{0})\). Therefore, the neighbors of \(y_{j}^{^{\prime }}\) must be colored by only three different colors. Since there exist exactly four \(4\)-cliques where each one of them contains two vertices of \(\{ y_{j}^{^{\prime }},~ 1\leqslant i\leqslant 4\}\), \(1\leqslant i\leqslant 4\), all \(4\)-cliques must be colored by the same set of colors. On the other hand, each vertex of \(\{y_{i},~ 1\leqslant i\leqslant 4\}\) is contained in exactly one of the four \(4\)-clique, this implies that all the \(4\)-cliques must be colored by the same set of colors \(\{ c(y_{i})\), \(1\leqslant i\leqslant 4\}\). So there exist at least two vertices \(x_{k}\) and \(y_{j}^{^{\prime }}\) that share the same color and their neighbors are colored by the same colors besides, the distance between each one of them and \(x_{0}\) is two, so they have the same color code, a contradiction.
Let \(S_{1}=\left\{ x_{0}\right\}\), \(S_{2}=\left\{ x_{2},y_{1}\right\}\), \(S_{3}=\left\{ x_{3},y_{2},y_{4}^{^{\prime }}\right\}\), \(S_{4}=\left\{x_{4},y_{3},y_{1}^{^{\prime }}\right\}\), \(S_{5}=\left\{x_{1},y_{4},y_{2}^{^{\prime }}\right\}\), and \(S_{6}=\left\{ y_{3}^{^{\prime }}\right\}\). Thus the coloring \(c\) defined by \(c:V( M(W_{4}))\longrightarrow \{ 1,\ldots,6\}\) such that \(c(u) =j\), for all \(u\in S_{j}\), is a locating \(6\)-coloring of \(M(W_{4})\). ◻
Theorem 8. For \(n\geqslant 5\), \(\chi _{L}(M(W_{n}))=n+1.\)
Proof. Since the vertices \(x_{0},y_{1},y_{2},y_{3},\ldots,y_{n}\) induce an \(n+1\)-clique, \(\chi_{L}(M(W_{n}))\geqslant n+1\).
Define, the coloring function \(c:V\left( M\left( W_{n}\right)\right) \longrightarrow \left\{ 1,2,\ldots,n+1\right\}\) in the following way: \[\begin{array}{l} c\left( x_{0}\right) =n+1, \quad c\left( y_{i}\right) =i, \quad 1\leqslant i\leqslant n,\\ \\ c\left( x_{1}\right) =n,\quad c\left( x_{i+1}\right) =i, \quad 1\leqslant i\leqslant n-1,\\ \\ c( y_{1}^{^{\prime }}) =n-1,\quad c\left( y_{2}^{^{\prime}}\right) =n, \quad c\left( y_{i+2}^{^{\prime }}\right) =i, \quad 1\leqslant i\leqslant n-2. \end{array}\] By using the coloring c, we obtain the following color codes of \(V(M( W_{n}))\) \[\begin{aligned} c_{\pi }\left( x_{0}\right) &=\left( 1,1,1,\ldots,0\right), \\ c_{\pi }\left( x_{i}\right) &=\left\{ \begin{array}{l} 0 \text{ for }j^{th}\text{ component }j\equiv i-1\pmod n, \\ 1 \text{ for }j^{th}\text{ component }j\equiv i, i-2\text{ or }i-3\pmod n,\\ 2 \text{ otherwise.} \end{array} \right. \\ c_{\pi }\left( y_{i}\right) &=\left\{ \begin{array}{l} 0\text{ for }i^{th}\text{ component }1\leqslant i\leqslant n, \\ 1\text{ otherwise.} \end{array} \right.\\ c_{\pi }\left( y_{i}^{^{\prime }}\right) &=\left\{ \begin{array}{l} 0 \text{ for }j^{th}\text{ component }j\equiv i-2\pmod n, \\ 1 \text{ for }j^{th}\text{ component }j\equiv i,i+1,i-1\text{ or } i-3\pmod n,\\ 2 \text{ otherwise.} \end{array} \right. \end{aligned}\] As a consequence, the coloring \(c\) is a locating \(n+1\)-coloring of \(M(W_{n})\). ◻
The gear graph \(G_{n}\) is a graph obtained by inserting an extra vertex between each pair of the adjacent vertices on the perimeter of the wheel graph \(W_{n}\). Let \(V\left( G_{n}\right) =\left\{x_{0},x_{1},x_{2},x_{3},\ldots,x_{n},z_{1},z_{2},\ldots,z_{n}\right\} ,\) \(x_{0}\) be the center vertex, the vertices \(\left\{x_{1},x_{2},x_{3},\ldots,x_{n}\right\}\) be on the rim and the other vertices \(z_{1},z_{2},z_{3},\ldots,z_{n-1}\) divide the edges \(x_{i}x_{i+1},\) \(1\leqslant i\leqslant n-1\), respectively and \(z_{n}\) be the subdivision of the edge \(\left\{ x_{n}x_{1}\right\}\) and \(E\left( G_{n}\right) =\left\{x_{0}x_{i},1\leqslant i\leqslant n\right\} \cup \left\{x_{i}z_{i},1\leqslant i\leqslant n\right\} \cup \left\{z_{i}x_{i+1},1\leqslant i\leqslant n-1\right\} \cup \left\{z_{n}x_{1}\right\}\).
The middle graph of the gear graph is given by subdividing each edge only once and joining all the middle vertices of the adjacent edges of \(G_{n}\). Denote the middle vertex of the edge \(x_{0}x_{i}\), where \(1\leqslant i\leqslant n\), by \(y_{i}\), the middle vertex of the edge \(x_{i}z_{i}\), where \(1\leqslant i\leqslant n\), by \(y_{i}^{\prime }\), the middle vertex of the edge \(z_{i}x_{i+1}\), where \(1\leqslant i\leqslant n-1\), by \(y_{i}^{^{\prime \prime }}\), and the middle vertex of the edge \(z_{n}x_{1}\), by \(y_{n}^{^{\prime \prime }}\). In this section, we determine the locating chromatic number of the middle graph of \(G_{n}\).
Theorem 9. For \(n=3\), \(\chi _{L}(M(G_{n}))=5\).
Proof. Since \(M(G_{3})\) contains at least two distinct \(4\)-cliques, \(\chi_{L}(M(G_{3}))\geqslant 5.\) Let \(S_{1}=\left\{ x_{0},x_{1},y_{3}^{^{\prime}},y_{1}^{^{\prime \prime }}\right\} ,\) \(S_{2}=\left\{ y_{1},y_{2}^{^{\prime\prime }},z_{3}\right\} ,\) \(S_{3}=\left\{ x_{3},y_{2},z_{2}\right\} ,\) \(S_{4}=\left\{ y_{3},y_{1}^{^{\prime }},y_{2}^{^{\prime }}\right\}\), and \(S_{5}=\left\{ x_{2},z_{1},y_{3}^{^{\prime \prime }}\right\}\). Clearly, the coloring \(c\) defined by \(c:V( M(G_{3})) \longrightarrow \{1,\ldots,5\}\) such that \(c(u) =j\), for all \(u\in S_{j}\), is a locating \(5\)-coloring of \(M(G_{3})\). ◻
Theorem 10. For \(n\geqslant 4\), \(\chi _{L}(M(G_{n}))=n+1\).
Proof. Since the vertices \(x_{0},y_{1},y_{2},y_{3},\ldots,y_{n}\) induce an \(n+1\)-clique, \(\chi_{L}(M(G_{n}))\geqslant n+1.\) For \(n=4\), let \(S_{1}=\left\{ x_{0},x_{1},y_{3}^{^{\prime }},y_{4}^{^{\prime }}\right\} ,\) \(S_{2}=\left\{ x_{4},z_{4},y_{1},y_{1}^{^{\prime \prime }}\right\} ,\) \(S_{3}=\left\{x_{2},x_{3},z_{1},z_{2},z_{3},y_{4},y_{4}^{^{\prime \prime }}\right\} ,\) \(S_{4}=\left\{ y_{3},y_{1}^{^{\prime }},y_{2}^{^{\prime }}\right\}\), and \(S_{5}=\left\{ y_{2},y_{2}^{^{\prime \prime }},y_{3}^{^{\prime \prime}}\right\}\). As a result, the coloring \(c\) defined by \(c:V( M(G_{4})) \longrightarrow \{1,\ldots,5\}\) such that \(c(u) =j\), for all \(u\in S_{j}\), is a locating \(5\)-coloring of \(M(G_{4})\). For \(n\geqslant 5\), define the coloring function \(c:V\left( M\left( G_{n}\right)\right) \longrightarrow \left\{ 1,2,\ldots,n+1\right\}\) in the following way: \[\begin{array}{l} c( x_{0}) =n+1, \quad c( y_{i}) =c( z_{i})=i, \quad 1\leqslant i\leqslant n, \\\\ c( x_{1})=c( y_{1}^{^{^{\prime \prime }}}) =n, \quad c( x_{i+1})=c( y_{i+1}^{^{^{\prime \prime }}})=i, \quad 1\leqslant i\leqslant n-1, \\ \\ c( y_{1}^{^{\prime }}) =n-2,\quad c(y_{2}^{^{\prime }}) =n-1, \quad c( y_{3}^{^{\prime}}) =n,\quad c( y_{i+3}^{^{\prime }}) =i, \quad 1\leqslant i\leqslant n-3. \end{array}\] Then the color codes of the vertices of \(M\left( G_{n}\right)\) are \[c_{\pi }\left( y_{i}\right) =\left\{ \begin{array}{l} 0\text{ for }i^{th}\text{ component }1\leqslant i\leqslant n, \\ 1\text{ otherwise.}% \end{array}% \right.\] \[c_{\pi }\left( z_{i}\right) =\left\{ \begin{array}{l} 0\text{ for }i^{th}\text{ component}, \\ 1\text{ for }j^{th}\text{ component }j\equiv i-1\text{ or } i-3\pmod n, \\ 2\text{ otherwise.} \end{array} \right.\] \[c_{\pi }\left( x_{i}\right) =\left\{ \begin{array}{l} 0 \text{ for }j^{th}\text{ component }j\equiv i-1\pmod n, \\ 1 \text{ for }j^{th}\text{ component }j\equiv i, i-2\text{ or }i-3\pmod n, \\ 2 \text{ otherwise.} \end{array} \right.\] \[c_{\pi }\left( y_{i}^{^{\prime }}\right) =\left\{ \begin{array}{l} 0 \text{for }j^{th}\text{ component }j\equiv i-3\pmod n, \\ 1 \text{ for }j^{th}\text{ component }j\equiv i,i-1\text{ or } i-2\pmod n, \\ 2 \text{ otherwise.} \end{array} \right.\] \[c_{\pi }\left( y_{i}^{^{\prime \prime }}\right) =\left\{ \begin{array}{l} 0 \text{ for }j^{th}\text{ component }j\equiv i-1\pmod n, \\ 1 \text{ for }j^{th}\text{ component }j\equiv i,i-2,i-3\text{ or\ }i+1\pmod n, \\ 2 \text{ otherwise.} \end{array} \right.\] Clearly, the coloring \(c\) is a locating \(n+1\)-coloring of \(M(G_{n})\). ◻
The helm graph \(H_{n}\) is obtained from an \(n\)-wheel graph by adjoining a pendant edge at each node of the cycle. Let \(V\left( H_{n}\right) =\left\{ x_{0},x_{1},x_{2},x_{3},\ldots,x_{n},x_{1}^{^{\prime }},\ldots,x_{n}^{^{\prime}}\right\} ,\) \(x_{0}\) be the center vertex, the vertices \(x_{1},x_{2},x_{3},\ldots,x_{n}\) be on the rim and other vertices \(x_{1}^{^{\prime }},x_{2}^{^{\prime }},\ldots,x_{n}^{^{\prime }}\) be the leaves and \(E(H_{n}) =\{ x_{0}x_{i},\text{ }1\leqslant i\leqslant n\} \cup \left\{ x_{i}x_{i+1},\text{ }1\leqslant i\leqslant n-1\left\} \cup \right\{ x_{n}x_{1}\right\} \cup \left\{ x_{i}x_{i}^{^{\prime }},\text{\ }1\leqslant i\leqslant n\right\}\).
The middle graph of the helm graph is given by subdividing each edge only once and joining all the middle vertices of adjacent edges of \(H_{n}\). Denote the middle vertex of the edge \(x_{0}x_{i}\), where \(1\leqslant i\leqslant n\), by \(y_{i}\), the middle vertex of the edge \(x_{i}x_{i+1}\), where \(1\leqslant i\leqslant n-1\), by \(y_{i}^{^{\prime }}\), the middle vertex of the edge \(x_{n}x_{1}\), by \(y_{n}^{^{\prime }}\) and the middle vertex of the edge \(x_{i}x_{i}^{^{\prime }}\), where \(1\leqslant i\leqslant n\), by \(y_{i}^{^{\prime \prime }}\). In this section, we determine the locating chromatic number of the middle graph of \(H_{n}\).
Theorem 11. For \(n=3\), \(\chi _{L}(M(H_{n}))=6\).
Proof. Note that the middle graph \(M(H_{3})\) contains at least two distinct \(5\)-cliques so, \(\chi _{L}(M(H_{3}))\geqslant 6.\) Let \(S_{1}=\left\{ y_{1},x_{2},x_{2}^{^{\prime }}\right\}\), \(S_{2}=\left\{y_{2},x_{3},x_{3}^{^{\prime }}\right\}\), \(S_{3}=\left\{y_{3},y_{2}^{^{\prime \prime }},x_{1},x_{1}^{^{\prime }}\right\}\), \(S_{4}=\left\{ y_{1}^{^{\prime }},y_{3}^{^{\prime \prime }}\right\}\), \(S_{5}=\left\{ y_{2}^{^{\prime }},y_{1}^{^{\prime \prime }}\right\}\), and \(S_{6}=\left\{ x_{0},y_{3}^{^{\prime }}\right\}\). As a consequence, the coloring \(c\) defined by \(c:V\left(M(H_{3})\right) \longrightarrow \left\{ 1,\ldots,6\right\}\), where \(c\left(u\right) =j\), for all \(u\in S_{j}\), is a locating \(6\)-coloring of \(M(H_{3}).\) ◻
Theorem 12. For \(n=4,5\), \(\chi _{L}(M(H_{n}))=n+2.\)
Proof. The vertices \(x_{0},y_{1},y_{2},\ldots,y_{n}\) induce an \(n+1\)-clique, \(\chi _{L}(M(H_{n}))\geqslant n+1\). For \(n=4\), the middle graph \(M(H_{n})\) contains at least two distinct \(5\)-cliques, so \(\chi _{L}(M(H_{4}))\geqslant 6\). For \(n=5\), assuming that \(\chi_{L}(M(H_{n}))=6\), then there exists a coloring function \(c:V(M(H_{5})) \longrightarrow \{ 1,\ldots,6\}\), such that for \(u,v\in V( M(H_{5}))\), we have \(c_{\pi }(u) \neq c_{\pi }(v)\). Since each \(y_{j}^{^{\prime }}\) where \(1\leqslant j\leqslant 4\), is a common vertex between two \(5\)-cliques, the neighbors of \(y_{j}^{^{\prime }}\) are colored by four or five colors. And so by the similar argument of proof of Theorem 7, we get a contradiction. Thus, \(\chi _{L}(M(H_{5}))\geqslant 7\).
Therefore, \(\chi _{L}(M(H_{n}))\geqslant n+2\). Now for \(n=4\), let \(S_{1}=\left\{ y_{1},y_{3}^{^{\prime }},y_{2}^{^{\prime \prime}}\right\} ,\) \(S_{2}=\left\{ y_{2},y_{1}^{^{\prime \prime }}\right\} ,\) \(S_{3}=\left\{ y_{3},x_{4},x_{4}^{^{\prime }}\right\} ,\) \(S_{4}=\left\{x_{3},x_{3}^{^{\prime }},y_{4},y_{1}^{^{\prime }}\right\} ,\) \(S_{5}=\left\{x_{0},x_{1},x_{1}^{^{\prime }},y_{2}^{^{\prime }},y_{4}^{^{\prime \prime}}\right\}\), and \(S_{6}=\left\{ x_{2},x_{2}^{^{\prime }},y_{4}^{^{\prime}},y_{3}^{^{\prime \prime }}\right\}.\) While, for \(n=5\), let \(S_{1}=\{ x_{2},x_{2}^{^{\prime }},y_{1},y_{3}^{^{\prime }}\}\), \(S_{2}=\{ x_{3},x_{3}^{^{\prime }},y_{2},y_{4}^{^{\prime }}\}\), \(S_{3}=\{ x_{4},x_{4}^{^{\prime }},y_{3},y_{5}^{^{\prime }}\}\), \(S_{4}=\{ x_{5},x_{5}^{^{\prime }},y_{4},y_{1}^{^{\prime }}\}\), \(S_{5}=\{ x_{1},x_{1}^{^{\prime }},y_{5},y_{2}^{^{\prime }}\}\), \(S_{6}=\{ x_{0}\}\), and \(S_{7}=\{ y_{1}^{^{\prime \prime}},y_{2}^{^{\prime \prime }},y_{3}^{^{\prime \prime }},y_{4}^{^{\prime\prime }}, y_{5}^{^{\prime \prime }}\}\).
Clearly, the coloring \(c\) defined by \(c:V\left(M(H_{n})\right) \longrightarrow \{ 1,\ldots,n+2\}\), where \(c\left(u\right) =j\), for all \(u\in S_{j}\), is a locating \(n+2\)-coloring of \(M(H_{n}).\) ◻
Theorem 13. For any positive integer \(n\geqslant 6\), \(\chi _{L}(M(H_{n}))=n+1.\)
Proof. The vertices \(x_{0},y_{1},y_{2},y_{3},\ldots,y_{n}\) induce an \(n+1\)-clique. Therefore, \(\chi _{L}(M(H_{n}))\geqslant n+1.\) Now, define the coloring function \(c:V\left( M\left( H_{n}\right)\right) \longrightarrow \left\{ 1,2,\ldots,n+1\right\}\) in the following way: \[\begin{array}{l} c\left( x_{0}\right) =n+1,\quad c\left( y_{i}\right) =i, \quad 1\leqslant i\leqslant n,\\ \\ c\left( x_{1}\right) =c\left( x_{1}^{^{\prime }}\right)=n, \quad c( x_{i+1}) = c\left(x_{i+1}^{^{\prime }}\right)=i,\quad 1\leqslant i<n, \\ \\ c\left( y_{1}^{^{\prime }}\right) =n-1,\quad c\left( y_{2}^{^{\prime}}\right) =n, \quad c\left( y_{i+2}^{^{\prime }}\right) =i,\quad 1\leqslant i\leqslant n-2, \\ \\ c\left( y_{1}^{^{\prime \prime }}\right) =n-3,~ c(y_{2}^{^{\prime \prime }}) =n-2,~ c( y_{3}^{^{\prime\prime }}) =n-1,~c( y_{4}^{^{\prime \prime }})=n,~ c\left( y_{i+4}^{^{\prime \prime }}\right) =i,~ 1\leqslant i\leqslant n-4. \end{array}\] Let \(\pi =\left\{ S_{1},S_{2},\ldots,S_{n+1}\right\}\) where \(S_{i}\) is the set of all vertices of the color \(i\). Then the color codes of the vertices of \(M\left(H_{n}\right)\) are \[\begin{aligned} c_{\pi }\left( y_{i}\right) &=\left\{ \begin{array}{l} 0\text{ for }i^{th}\text{ component}, \\ 1\text{ otherwise.} \end{array} \right.\\ c_{\pi }\left( x_{i}^{^{\prime }}\right) &=\left\{ \begin{array}{l} 0\text{ for }j^{th}\text{ component }j\equiv i-1\pmod n, \\ 1\text{ for }j^{th}\text{ component }j\equiv i-4\pmod n, \\ 2\text{ otherwise.} \end{array} \right.\\ c_{\pi }\left( x_{i}\right) &=\left\{ \begin{array}{l} 0\text{ for }j^{th}\text{ component }j\equiv i-1\pmod n, \\ 1\text{ for }j^{th}\text{ component }j\equiv i,i-2,i-3\text{ or } i-4\pmod n, \\ 2\text{ otherwise.} \end{array} \right.\\ c_{\pi }\left( y_{i}^{^{\prime }}\right) &=\left\{ \begin{array}{l} 0\text{ for }j^{th}\text{ component }j\equiv i-2\pmod n, \\ 1\text{ for }j^{th}\text{ component }j\equiv i-4,i-3,i-1,i\text{ or } i+1\pmod n, \\ 2\text{ otherwise.} \end{array} \right.\\ c_{\pi }\left( y_{i}^{^{\prime \prime }}\right) &=\left\{ \begin{array}{l} 0\text{ for }j^{th}\text{ component }j\equiv i-4\pmod n, \\ 1\text{ for }j^{th}\text{ component }j\equiv i,i-1,i-2\text{ or } i-3\pmod n, \\ 2\text{ otherwise.} \end{array} \right. \end{aligned}\] As consequence, this coloring \(c\) is definitely a locating \(n+1\)-coloring of \(M(H_{n}).\) ◻