Locating Chromatic Number of Middle Graph of Path, Cycle, Star, Wheel, Gear and Helm Graphs

Proof. Since $M(P_n)$ contains $3$-clique, $3⩽\chi (M(P_n))⩽{\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))⩾4$.

Define the coloring function $c:V(M(P_n))⟶\{1,2,3,4\}$ as follows: $$c(x_i)=\{\begin{array}{l}1\text{if}i=1,\\ 2\text{if}i\equiv 0(\mathrm{mod}3)\text{and}1⩽i⩽n,\\ 3\text{if}i\equiv 2(\mathrm{mod}3)\text{and}1⩽i⩽n,\\ 4\text{if}i\equiv 1(\mathrm{mod}3)\text{and}2⩽i⩽n.\end{array}$$ $$c(y_i)=\{\begin{array}{l}2\text{if}i\equiv 1(\mathrm{mod}3)\text{and}1⩽i⩽n,\\ 3\text{if}i\equiv 0(\mathrm{mod}3)\text{and}1⩽i⩽n,\\ 4\text{if}i\equiv 2(\mathrm{mod}3)\text{and}1⩽i⩽n.\end{array}$$

Hence, we obtain a partition $\pi =\{S_1,S_2,S_3,S_4\}$ of $V(M(P_n))$, where $S_1=\{x_1\}$, $S_2=\{x_3,x_6,\dots \}\cup \{y_1,y_4,\dots \}$, $S_3=\{x_2,x_5,\dots \}\cup \{y_3,y_6,\dots \}$, and $S_4=\{x_4,x_7,\dots \}\cup \{y_2,y_5,\dots \}$.

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,\dots ,n-1\}$. Since $x_i$ and $y_i$ belong to different color classes, it follows that $d(u,S_1)\ne 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)$. 

Proof. Since the graph $M(C_n)$ contains a $3$-clique, ${\chi }_L(M(C_n))⩾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. 

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=\{x_3,x_8\},$ $S_2=\{x_1,x_4\},$ $S_3=\{x_2,x_6\}$ and $S_4=\{x_5,x_7\}$. If $n=5,$ let $S_1=\{x_3,x_6,x_{10}\},$ $S_2=\{x_1,x_4,x_7\},$ $S_3=\{x_2,x_9\}$ and $S_4=\{x_5,x_8\}$. If $n=6,$ let $S_1=\{x_3,x_6,x_{12}\},$ $S_2=\{x_1,x_4,x_7,x_9\},$ $S_3=\{x_2,x_{10}\}$ and $S_4=\{x_5,x_8,x_{11}\}$. If $n=7,$ let $S_1=\{x_3,x_6,x_{14}\},$ $S_2=\{x_1,x_4,x_7,x_{10}\},$ $S_3=\{x_2,x_9,x_{12}\}$ and $S_4=\{x_5,x_8,x_{11},x_{13}\}$. If $n=8,$ let $S_1=\{x_3,x_6,x_{13},x_{16}\},$ $S_2=\{x_1,x_4,x_7,x_{10}\},$ $S_3=\{x_2,x_9,x_{12},x_{15}\}$, and $S_4=\{x_5,x_8,x_{11},x_{14}\}$. Clearly $\pi =\{S_1,S_2,S_3,S_4\}$ is a partition of $V(M(C_n))$, where $3⩽n⩽8$. Therefore, the coloring $c$ defined by $c:V(M(C_n))\to \{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)$. 

Proof.

1. Let $S_i$ be the set of vertices that received the color $i$, $1⩽i⩽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⩽j⩽4$ and $i\ne 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.

2. 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.

3. Assume that for $j=1$, $\left|S_j\right|=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$.

4. Assume that there exists $x_l\in S_i$ such that $d_{M(C_n)}(x_l,S_j)⩾3$ for some $j\ne 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)⩾3$ and$d_{M(C_n)}(x_l,x_t)⩾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,,\dots ,x_l,\dots ,x_{t-1},x_t\}$. Therefore, $d_{M(C_n)[R]}(x_k,S_i)=2$ whenever $k\in \{s+1,s+2,t-1,t-2\}$. By part $2$, we get a contradiction. Hence $d_{M(C_n)\left[R\right]}(x_l,S_j)⩽2$ and so, $d_{M(C_n)}(x_l,S_j)⩽2$.

Proof. Assume that ${\chi }_L(M(C_n))=4$. Let $c$ be a locating coloring and $\{S_i$, $1⩽i⩽4\}$ be the set of the color classes, say that $S_1$ is of minimum cardinality. Now, let $S=V(M(C_n))╲S_1$, by part $1$ of Lemma 1 there exist $m$ vertices in $S$ where $m⩽3$ such that the distance between each one of them and $S_1$ is two. So there exist $\left|S\right|-m$ vertecies such that $d_{M(C_n)}(x_i,S_1)=1,$ $1⩽i⩽2n$. If $u\in S_2$, then by part $4$ of Lemma 1, $d_{M(C_n)}(u,S_j)⩽2$ for $j=3,4$. Hence $c_{\pi }\left(u\right)=(1,0,k,d)$, where $k,d\in \{1,2\}$. 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 $$\begin{gathered} \left|S\right|-3⩽\left|S\right|-m⩽9 \\ \iff \left|S\right|⩽12 \\ \iff 2n-\left|S_1\right|⩽12, \end{gathered}$$ where $4\left|S_1\right|⩽2n$. So $n⩽8$, contradiction. Hence ${\chi }_L(M(C_n))⩾5$, for all $n⩾9$. Now, define the coloring function $c:V(M(C_n))⟶\{1,2,3,4,5\}$ as follows:

1. If $n\equiv 0(\mathrm{mod}4)$, then $$c(x_i)=\{\begin{array}{l}1,\text{if }i=2n,\\ 2,\text{if }i\equiv 1(\mathrm{mod}4)\text{ and }i⩽n+1\text{ or }i\equiv 0(\mathrm{mod}4)\text{ and }n+1<i<2n,\\ 3,\text{if }i\equiv 2(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 1(\mathrm{mod}4)\text{ and }n<i<2n,\\ 4,\text{if }i\equiv 3(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 2(\mathrm{mod}4)\text{ and }n<i<2n,\\ 5,\text{if }i\equiv 0(\mathrm{mod}4)\text{ and }i⩽n\text{ or }i\equiv 3(\mathrm{mod}4)\text{ and }n<i<2n.\end{array}$$

2. If $n\equiv 1(\mathrm{mod}4)$, then $$c(x_i)=\{\begin{array}{l}1,\text{if }i=2n,\\ 2,\text{if }i\equiv 1(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 2(\mathrm{mod}4)\text{ and }n<i<2n,\\ 3,\text{if }i\equiv 2(\mathrm{mod}4)\text{ and }i<n,i=n\text{ or }i\equiv 3(\mathrm{mod}4)\text{ and }n<i<2n,\\ 4,\text{if }i=3(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 0(\mathrm{mod}4)\text{ and }n<i<2n,\\ 5,\text{if }i\equiv 0(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 1(\mathrm{mod}4)\text{ and }n<i<2n.\end{array}$$

3. If $n\equiv 2(\mathrm{mod}4)$, then $$c(x_i)=\{\begin{array}{l}1,\text{if }i=2n,\\ 2,\text{if }i\equiv 1(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 0(\mathrm{mod}4)\text{ and }n<i<2n,\\ 3,\text{if }i\equiv 2(\mathrm{mod}4)\text{ and }i⩽n\text{ or }i\equiv 1(\mathrm{mod}4)\text{ and }n<i<2n,\\ 4,\text{if }i\equiv 3(\mathrm{mod}4)\text{ and }i⩽n+1\text{ or }i\equiv 2(\mathrm{mod}4)\text{ and }n+1<i<2n,\\ 5,\text{if }i\equiv 0(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 3(\mathrm{mod}4)\text{ and }n<i<2n.\end{array}$$

4. If $n\equiv 3(\mathrm{mod}4)$, then $$c(x_i)=\{\begin{array}{l}1,\text{if }i=2n,\\ 2,\text{if }i\equiv 1(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 2(\mathrm{mod}4)\text{ and }n<i<2n,\\ 3,\text{if }i\equiv 2(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 3(\mathrm{mod}4)\text{ and }n<i<2n,\\ 4,\text{if }i\equiv 3(\mathrm{mod}4)\text{ and }i<n\text{ or }i\equiv 0(\mathrm{mod}4)\text{ and }n<i<2n,\\ 5,\text{if }i\equiv 0(\mathrm{mod}4)\text{ and }i<n,i=n\text{ or }i\equiv 1(\mathrm{mod}4)\text{ and }n<i<2n.\end{array}$$

In all the above four cases $\pi =\{S_1,S_2,S_3,S_4,S_5\}$ is a partition of $V(M(C_n))$ and for any two distinct vertices $u_i$ and $u_j$ in $S_l$ with $2⩽l⩽5$, $d(u_i,S_1)\ne d(u_j,S_1)$, hence $c_{\pi }\left(u_i\right)\ne c_{\pi }\left(u_j\right)$. Therefore, all vertices in $M(C_n)$ have distinct color codes. 

Proof. The vertices $x_0,x_1,x_2,x_3,\dots ,x_n$ have distinct colors since they induce an $n+1$-clique. Therefore, ${\chi }_L(M(K_{1,n}))⩾n+1.$

Now, define the coloring function $c:V\left(M\left(K_{1,n}\right)\right)⟶\{1,2,\dots ,n+1\}$ in the following way: $$c\left(x_0\right)=c\left(x_i\right)=n+1,c\left(y_i\right)=i,1⩽i⩽n.$$ By using the coloring $c$, we obtain the following color codes of $V(M(K_{1,n}))$ $$c_{\pi }\left(x_0\right)=(1,1,1,\dots ,0),$$ $$c_{\pi }\left(x_i\right)=\{\begin{array}{l}0\text{ for }{(n+1)}^{th}\text{ component,}\\ 1\text{ for }{i}^{th}\text{ component }1⩽i⩽n,\\ 2\text{otherwise.}\end{array}$$ $$c_{\pi }\left(y_j\right)=\{\begin{array}{l}0\text{ for }{j}^{th}\text{ component }1⩽j⩽n,\\ 1\text{ otherwise.}\end{array}$$ As a result, this coloring $c$ is indeed a locating $n+1$-coloring of $M(W_n).$ 

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))⩾5$. If ${\chi }_L(M(W_3))=5$, then there exist at least two vertices of $\{y_j,y_k^{{}^{\mathrm{\prime }}}:1⩽j,k⩽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^{{}^{\mathrm{\prime }}}\right)$. Since $N\left(y_j\right)\cap N\left(y_k^{{}^{\mathrm{\prime }}}\right)=\{y_i,1⩽i⩽3\}\cup \{y_l^{{}^{\mathrm{\prime }}},1⩽l⩽3\}╲\{y_j,y_k^{{}^{\mathrm{\prime }}}\}$, we get $c_{\pi }(y_j)=c_{\pi }(y_k^{{}^{\mathrm{\prime }}}),$ a contradiction.

Case 2: Two repeated colors.

Let $c\left(y_1\right)=c\left(y_2^{{}^{\mathrm{\prime }}}\right)=1$, $c\left(y_2\right)=c\left(y_3^{{}^{\mathrm{\prime }}}\right)=2$, $c\left(y_3\right)=3$, and $c\left(y_1^{{}^{\mathrm{\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^{{}^{\mathrm{\prime }}})$ or $c_{\pi }(y_2)=c_{\pi }(y_3^{{}^{\mathrm{\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^{{}^{\mathrm{\prime }}}\right)=1$, $c\left(y_2\right)=c\left(y_3^{{}^{\mathrm{\prime }}}\right)=2$, and $c(y_3)=c(y_1^{{}^{\mathrm{\prime }}})=3$. Clearly, $c(x_i)\in \{4,5\}$ for $0⩽i⩽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))⩾6$. Let $S_1=\left\{x_0\right\},$ $S_2=\{y_1,x_2\}$, $S_3=\{y_2,x_3\},$ $S_4=\{y_3,y_1^{{}^{\mathrm{\prime }}}\}$, $S_5=\left\{y_3^{{}^{\mathrm{\prime }}}\right\},$ and $S_6=\{x_1,y_2^{{}^{\mathrm{\prime }}}\}$, then the coloring $c$ defined by $c:V(M(W_3))⟶\{1,\dots ,6\}$ such that $c\left(u\right)=j$ for all $u\in S_j$ is a locating $6$-coloring of $M(W_3)$.

Proof. The vertices $x_0,y_1,y_2,y_3,y_4$ induce a $5$-clique, so ${\chi }_L(M(W_4))⩾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^{{}^{\mathrm{\prime }}},$ $1⩽j⩽4$, are colored by three or four colors since each $y_j^{{}^{\mathrm{\prime }}}$ is a common vertex between two $4$-cliques. If there is $y_j^{{}^{\mathrm{\prime }}}$ such that its neighbor colors set is $\{1,2,3,4,5\}\setminus \{c(y_j^{{}^{\mathrm{\prime }}})\}$, then $c_{\pi }(y_j^{{}^{\mathrm{\prime }}})=c_{\pi }(y_i)$ or $c_{\pi }(y_j^{{}^{\mathrm{\prime }}})=c_{\pi }(x_0)$. Therefore, the neighbors of $y_j^{{}^{\mathrm{\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^{{}^{\mathrm{\prime }}},1⩽i⩽4\}$, $1⩽i⩽4$, all $4$-cliques must be colored by the same set of colors. On the other hand, each vertex of $\{y_i,1⩽i⩽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⩽i⩽4\}$. So there exist at least two vertices $x_k$ and $y_j^{{}^{\mathrm{\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=\{x_2,y_1\}$, $S_3=\{x_3,y_2,y_4^{{}^{\mathrm{\prime }}}\}$, $S_4=\{x_4,y_3,y_1^{{}^{\mathrm{\prime }}}\}$, $S_5=\{x_1,y_4,y_2^{{}^{\mathrm{\prime }}}\}$, and $S_6=\left\{y_3^{{}^{\mathrm{\prime }}}\right\}$. Thus the coloring $c$ defined by $c:V(M(W_4))⟶\{1,\dots ,6\}$ such that $c(u)=j$, for all $u\in S_j$, is a locating $6$-coloring of $M(W_4)$.