A proper \(k\)-coloring \(\alpha\) of a graph \(G\) induces a partition \(\Pi = \{C_1, C_2, \dots, C_k\}\), where \(C_i = \{v \in V(G) \mid \alpha(v) = i\}\). The color code of a vertex \(v \in V(G)\) with respect to \(\Pi\) is defined as the tuple \(c_{\Pi}(v) = (d(v, C_1), d(v, C_2), \dots, d(v, C_k))\), where \(d(v, C_i)\) represents the distance from \(v\) to the set \(C_i\). A proper \(k\)-coloring \(\alpha\) is called a locating \(k\)-coloring of \(G\) if \(\alpha\) induces a partition \(\Pi\) such that for any two distinct vertices \(u, v \in V(G)\), it holds that \(c_{\Pi}(u) \neq c_{\Pi}(v)\). The locating chromatic number of \(G\), denoted \(\chi_L(G)\), is the smallest \(k\) for which a locating \(k\)-coloring of \(G\) exists. In this paper, we establish a connection between the locating \(k\)-coloring of \(C_n(1,2,\dots,t) + K_m\) and the union of graphs \(\bigcup_{i=1}^p C_{n_i} + K_m\), leveraging properties of simple cycles in directed graphs. Using this connection, we determine the locating chromatic number of \(C_n(1,2,\dots,t) + K_m\) for \(t = 2\) and \(n \in [6, 28]\), as well as for \(t = 3\) and \(n \in [8, 24]\).
Let \(G = (V,E)\) be a finite and simple graph. The distance \(d(u,v)\) between vertices \(u\) and \(v\) in \(G\) is the length of a shortest path between vertices \(u\) and \(v\) in \(G\). For a set \(S \subseteq V(G)\), the distance between \(u\) and \(S\) is given by \(d(u,S) = \min\{d(u,v) \ | \ v \in S\}\).
For a natural number \(k\), let \(\alpha : V(G) \to [1,k]\) be a proper vertex \(k\)-coloring of a simple graph \(G\). Naturally, the coloring \(\alpha\) will induce a partition \(\Pi = \{C_1,C_2,…,C_k\}\) with \(C_i = \{v \in V(G) \ | \ \alpha(v) = i\}\). Under the coloring \(\alpha\) in \(G\), define the color code \(c_{\Pi}(v)\) of a vertex \(v\) as \((d(v,C_1),d(v,C_2),…,d(v,C_k))\). If for every two distinct vertices \(u\) and \(v\) we have that \(c_{\Pi}(u) \ne c_{\Pi}(v)\), then \(\alpha\) is called a locating \(k\)-coloring. The locating-chromatic number of \(G\), denoted by \(\chi_L(G)\), is the smallest \(k\) such that \(G\) admits a locating \(k\)-coloring.
The concept of graph locating chromatic number was first introduced by Chartrand et al. [5], marking the beginning of an active area of research in graph theory. Since then, the locating chromatic numbers of various graph classes have been extensively studied. Significant contributions include investigations on star amalgamations [1], complete \(n\)-ary trees [13], powers of paths and cycles [6], subdivisions of friendship graphs [10], Möbius ladders [9], barbell shadow paths [2], and \(m\)-shadows of connected graphs [12]. Furthermore, the study has been extended to infinite trees [7], with a detailed characterization of trees having a locating chromatic number 3 presented in [3]. For an extensive survey of locating colorings and their variations, the reader is directed to [8]. Behtoei and Anbarloei [4] further advanced this field by examining locating colorings for join graphs through the lens of adjacency locating coloring. Selected results from their work are presented below.
Theorem 1.1. [4] For two positive integers \(m \ge 2\) and \(n \ge 3\), let \(m_0 = \min\{k \in \mathbb{N} \ | \ m \le \frac{1}{2}k^2(k – 1)\) and \(n_0 = \min\{k \in \mathbb{N} \ | \ n \le \frac{1}{2}k^2(k – 1)\). Then, \[\begin{aligned} \chi_L(P_m + C_n) = \begin{cases} m_0 + \chi_L(C_n), & \text{if } 3 \le n < 9,\\ m_0 + n_0, & \text{if } n \ge 9, n \ne \frac{1}{2}k^2(k-1) – 1,\\ m_0 + n_0 + 1, & \text{if } n \ge 9, n = \frac{1}{2}k^2(k-1) – 1. \end{cases} \end{aligned}\]
Theorem 1.2. [4] For two positive integers \(m \ge 2\) and \(n \ge 3\), let \(n_0 = \min\{k \in \mathbb{N} \ | \ n \le \frac{1}{2}k^2(k – 1)\). Then, \[\begin{aligned} \chi_L(K_m + C_n) = \begin{cases} m + \chi_L(C_n), & \text{if } 3 \le n < 9,\\ m + n_0, & \text{if } n \ge 9, n \ne \frac{1}{2}k^2(k-1) – 1,\\ m + n_0 + 1, & \text{if } n \ge 9, n = \frac{1}{2}k^2(k-1) – 1. \end{cases} \end{aligned}\]
In particular, the locating chromatic number of the wheel \(W_n\) is \(\chi_L(K_1 + C_n)\).
For two integers \(n\) and \(k\), a de Bruijn sequence of order \(n\) over an alphabet \(A\) of size \(k\) is defined as a cyclic sequence \(b_1b_2 \dots b_m\) such that every possible \(n\)-string over \(A\) appears exactly once as a continuous subsequence [11]. For example, \(00010111\) is the de Bruijn sequence with \(n = 3\) and \(A = \{0,1\}\) since \[\begin{aligned} b_1b_2b_3 & = 000, & b_2b_3b_4 & = 001, & b_3b_4b_5 & = 010, & b_4b_5b_6 & = 101,\\ b_5b_6b_7 & = 011, & b_6b_7b_8 & = 111, & b_7b_8b_1 & = 110, & b_8b_1b_2 & = 100. \end{aligned}\]
A de Bruijn digraph \(\overrightarrow{B_{n,k}}\) is defined as a digraph with the vertex set \[\begin{aligned} V(\overrightarrow{B_{n,k}}) & = \{b_1b_2…b_n \ | \ b_i \in [0,k-1], i \in [1,n]\}, \end{aligned}\] and the arc set \[\begin{aligned} A(\overrightarrow{B_{n,k}}) & = \{(b_1b_2…b_n,b_2b_3…b_{n+1}) \ | \ b_i \in [0,k-1], i \in [1,n+1]\}. \end{aligned}\] Then, de Bruijn sequence can be constructed by finding a Hamiltonian path on de Bruijn digraph having dimension \(n\) over an alphabet of size \(k\).
In this paper, we establish a connection between the locating \(k\)-coloring of \(C_n(1,2,…,t) + K_m\) and \(\cup_{i=1}^p C_{n_i} + K_m\) with simple cycles in a subgraph of de Bruijn graph. In particular, using this connection, we compute the exact value of \(\chi_L(C_n(1,2,…,t) + K_m)\) for \(t = 2, n \in [6,28]\) and \(t = 3, n \in [8,24]\) with the help of a computer program.
Let \(n,t\) be positive integers with \(t \le n-1\). Let \(C_n(1,2,\ldots,t)\) be a circulant graph on \(n\) vertices with parameters \(1,2,\ldots,t\). Let \(G = C_n(1,2,…,t) + K_m\) be the join product of two graphs with the vertex set \[\begin{aligned} V(G) = \{v_i,u_l \ | \ i \in [1,n], l \in [1,m]\}, \end{aligned}\] and the edge set \[\begin{aligned} E(G) = \{v_iv_{i+r}, v_iu_l \ | \ i \in [1,n], r \in [1,t], l \in [1,m]\} \cup \{u_pu_l \ | \ p,l \in [1,m], p \ne l\}, \end{aligned}\] with indices \(i\) and \(r\) taken modulo \(n\). The vertices \(v_i\) for \(i \in [1,n]\) are called outer vertices.
In this section, we deal with the lower bound on the locating chromatic number of \(C_n(1,2,…,t) + K_m\).
Theorem 2.1. For any \(n \ge 3\), \(\chi_L(C_n(1,2, \dots,t) + K_m) \ge k+m\) where \(k\) is the smallest integer such that \(n \le k\sum\limits_{i=t}^{2t} \binom{k-1}{i}\).
Proof. Let \(G \cong C_n(1,2,…,t) + K_m\). Let \(\alpha\) be locating \((k+m)\)-coloring of \(G\) which induces a partition \(\Pi\). Since every vertex \(u_l\) is adjacent to all vertices of \(G\) and \(\alpha\) is proper, \(u_l\) must have a unique color in \(G\). In addition, since \(diam(G) = 2\), it holds that \(1 \le d(u,v) \le 2\) for every distinct vertices \(u\) and \(v\) in \(V(G)\).
Let \(\mathcal{P}(X)\) denote the power set of \(X\). By the construction of \(G\), every outer vertex \(v_i\) is adjacent to other vertices that are colored with at least \(t\) colors and at most \(2t\) colors. For every \(v_i \in V(G)\) which is adjacent to \(q\) colors, there exists exactly one set \(A \in \mathcal{P}([1,k]\setminus \{i\})\) with \(|A| = q\) which implies that \(c_{\Pi}(v_i) = (a_1,a_2,…,a_{k+m})\) with \[\begin{aligned} a_j = \begin{cases} 0, & \text{if } j = i,\\ 1, & \text{if } j \in A \text{ or } j \in [k+1,k+m],\\ 2, & \text{otherwise}. \end{cases} \end{aligned}\]
Therefore, counting all possible color codes of \(v_i\) will be equivalent to counting all possible set \(A\). Without loss of generality, let \(v_i\) be colored by \(1\). Since \(v_i\) is adjacent to at least \(t\) colors and at most \(2t\) colors, the number of possible sets of \(A\) is \[\begin{aligned} \binom{k-1}{t} + \binom{k-1}{t+1} + … + \binom{k-1}{2t}. \end{aligned}\]
By also considering the possible color of \(v_i\), replacing the color of \(v_i\) with other colors, altogether the number of possible color codes of \(v_i\) is \[\begin{aligned} k\bigg(\binom{k-1}{t} + \binom{k-1}{t+1} + … + \binom{k-1}{2t}\bigg) = k\sum\limits_{i=t}^{2t} \binom{k-1}{i}. \end{aligned}\]
Since the number of vertices \(v_i\) cannot exceed the number of possible \(v_i\) color codes, we obtain \[\begin{aligned} n \le k\sum\limits_{i=t}^{2t} \binom{k-1}{i}. \end{aligned}\]
As a result, it follows that \(\chi_L(C_n(1,2,…,t) + K_m) \ge k + m\) with \(k\) is the smallest integer such that \(n \le k\sum\limits_{i=t}^{2t} \binom{k-1}{i}\). ◻
We will give an example of obtaining a lower bound on \(\chi_L(C_{60}(1,2) + K_m)\). Consider \(k=5\). Without loss of generality, consider vertices colored by 1. One possible sequence of colors in five consecutive outer vertices is 32132 or 23123, but these two possibilities are considered to be the same. Hence, all possible sequences are 32132, 42142, 52152, 43143, 53153, 54154 (which is equivalent to choosing two numbers from 2,3,4,5), 23142, 24152, 34153, 23153 (choosing three numbers from 2,3,4,5), 23145 (choosing four numbers from 2,3,4,5). Then, the number of all possible sequences of colors in five consecutive vertices with 1 in the middle is \(\binom{4}{2}+ \binom{4}{3} + \binom{4}{4}=11\). Therefore, we have \(5\sum\limits_{i=2}^4\binom{4}{i}=5(\binom{4}{2}+ \binom{4}{3} + \binom{4}{4})=5 \times 11=55\). Since \(60 > 55 = 5\sum\limits_{i=2}^4\binom{4}{i}\), then the smallest integer \(k\) that satisfies \(n \le k\sum\limits_{i=2}^4\binom{k-1}{i}\) is \(6\). Therefore, \(\chi_L(C_{60}(1,2) + K_m) \ge 6 + m\). In general, \(\chi_L(C_n(1,2) + K_m) \ge 6 + m\) for \(n \ge 56\).
Remark 2.2. With similar arguments, it also holds that \(\chi_L(\cup_{i=1}^p C_{n_i} + K_m) \ge k^* + 1\) for \(n = \sum\limits_{i=1}^p n_i\). Furthermore, it also holds if \(K_m\) is replaced by \(\overline{K_m}\).
Consider a locating coloring of wheel graph \(W_n \cong C_n + K_1\). Take the coloring of outer vertices and consider them as a cyclic sequence. This cyclic sequence has a property that every subsequence with length \(3\) is unique along within the cyclic sequence. This phenomenon is similar to de Bruijn sequence.
Hence, we can construct a new directed graph similar with the construction of de Bruijn graph and has a connection to the locating coloring of wheel graph. For \(k \ge 3\), let a digraph \(\overrightarrow{K^3_k}\) be defined with the vertex set \[\begin{aligned} V(\overrightarrow{K^3_k}) = \{s_1s_2s_3 \ | \ s_i \in [1,k], s_i \ne s_{i+1}, i \in [1,2]\}, \end{aligned}\] and the arc set \[\begin{aligned} A(\overrightarrow{K^3_k}) = \{(s_1s_2s_3,s_2s_3s_4) \ | \ s_i \in [1,k], s_i \ne s_{i+1}, i \in [1,3]\}. \end{aligned}\]
This graph is called Kautz digraph \(K^{n}_k\) with \(n = 3\) [11]. Notice that the ways to construct de Bruijn digraph and Kautz digraph are similar. Vertices in both of the graphs are represented by sequences of numbers. However, in Kautz digraph only sequences with distinct neighboring terms are allowed. This implies that the Kautz digraph \(\overrightarrow{K^{n}_k}\) is a subgraph of de Bruijn digraph \(\overrightarrow{B_{n,k}}\).
Let \(\pi(\overrightarrow{K^3_k})\) be a partition of Kautz digraph \(\overrightarrow{K^3_k}\) such that two vertices \(r_1r_2r_3\) and \(s_1s_2s_3\) belong to the same class partition if \(s_1s_2s_3 = r_3r_2r_1\). For example, consider the digraph \(\overrightarrow{K^3_3}\). It holds that \(\pi(\overrightarrow{K^3_3}) = \bigcup_{i=1}^9 Q_i\) where \[\begin{aligned} Q_1 & = \{123,321\}, & Q_4 & = \{121\}, & Q_7 & = \{232\},\\ Q_2 & = \{231,132\}, & Q_5 & = \{131\}, & Q_8 & = \{313\},\\ Q_3 & = \{312,213\}, & Q_6 & = \{212\}, & Q_9 & = \{323\}. \end{aligned}\]
We present the illustration of the digraph \(\overrightarrow{K^3_3}\) along with its partition in Figure 1. With this additional property, we are able to find locating \((k+1)\)-coloring from certain cycles in Kautz digraph \(\overrightarrow{K^3_k}\).
Theorem 3.1. Let \(n \ge 3\). We have \(\chi_L(W_n) \le k+1\) if and only if there exists a directed cycle \(\overrightarrow{C_n} \subseteq \overrightarrow{K^3_k}\) such that the subgraph \(\overrightarrow{C_n}\) contains at most one vertex in each class partition \(\pi(\overrightarrow{K^3_k})\).
Proof. Let \(v_1,v_2,…,v_n\) be the outer vertices and \(u\) be the center of \(W_n\). For the forward direction, let \(W_n\) has a locating coloring \(\alpha : V(W_n) \to \mathbb{Z}\) with \(k+1\) colors such that \(c_{\Pi}(x) \ne c_{\Pi}(y)\) for every \(x,y \in V(W_n)\). Let \(a_i = \alpha(v_i)\alpha(v_{i+1})\alpha(v_{i+2})\) and \(a'_i = \alpha(v_{i+2})\alpha(v_{i+1})\alpha(v_i)\) for \(i \in [1,n]\) taken modulo \(n\). Now, construct a digraph \(\overrightarrow{H}\) with the vertex set \[\begin{aligned} V(\overrightarrow{H}) = \{a_i \ | \ i \in [1,n]\}, \end{aligned}\] and the arc set \[\begin{aligned} A(\overrightarrow{H}) = \{(a_i,a_{i+1}) \ | \ i \in [1,n]\}, \end{aligned}\] where the index is taken modulo \(n\). If there exists distinct \(i,j \in [1,n]\) where \(a_i = a_j\) or \(a_i = a'_j\), then \(c_{\Pi}(a_i) = c_{\Pi}(a_j)\). Since \(\alpha\) is a locating coloring, it holds that \(a_i \ne a_j,\) and \(a_i \ne a'_j,\) for every \(i,j \in [1,n], i \ne j\) which are taken modulo \(n\). This implies that if \(a_i \in V(\overrightarrow{H})\), then \(a_i \in V(\overrightarrow{K^3_k})\) and \(a_i\) is a unique vertex in the class partition \(\pi(\overrightarrow{K^3_k})\).
Therefore, \(\overrightarrow{H} \subseteq \overrightarrow{K^3_k}\) and \(\overrightarrow{H} \cong \overrightarrow{C_n}\) which contains at most one vertex in each class partition \(\pi(\overrightarrow{K^3_k})\).
For the backward direction, let \(\overrightarrow{H}\) be a subgraph of \(\overrightarrow{K^3_k}\) which is isomorphic to \(\overrightarrow{C_n}\) containing at most one vertex in each class partition \(\pi(\overrightarrow{K^3_k})\). Let \(s_1s_2s_3\) be a vertex of \(\overrightarrow{H} \subseteq \overrightarrow{K^3_k}\). By the definition of the Kautz digraph, for every \(i \in [1,n]\) where \(s_i,s_{i+1},s_{i+2} \in [1,k]\) if \(s_is_{i+1}s_{i+2} \in V(\overrightarrow{H})\) and \((s_is_{i+1}s_{i+2},x) \in A(\overrightarrow{H})\), then \(x = s_{i+1}s_{i+2}s_{i+3}\) for some \(s_{i+3} \in [1,k]\). Here, we have a cyclic sequence \(s_1,s_2,s_3,\ldots,s_n\) where \(s_i \in [1,k]\) for every \(i \in [1,n]\). Since the subgraph \(\overrightarrow{H}\) contains at most one vertex in each class partition \(\pi(\overrightarrow{K^3_3})\), we have \[\begin{aligned} \label{res_wheel}\begin{cases} (s_i,s_{i+1},s_{i+2}) & \ne (s_j,s_{j+1},s_{j+2}),\\ (s_i,s_{i+1},s_{i+2}) & \ne (s_{j+2},s_{j+1},s_j),\end{cases} \end{aligned} \tag{1}\] for every \(i,j \in [1,n], i \ne j\). Let \(\alpha : V(W_n) \to [1,k+1]\) be a coloring of \(W_n\) with \[\begin{aligned} \alpha(v_i) = s_i, \end{aligned}\] for \(i \in [1,n]\) and \(\alpha(u) = k+1\). This coloring induces a partition \(\Pi\). By Eq. 1, \(c_{\Pi}(x) \ne c_{\Pi}(y)\) for every \(x,y \in V(W_n)\). This implies that \(\chi_L(W_n) \le k + 1.\) ◻
In Figure 2, we illustrate a locating coloring of \(C_7 + K_1\) and the corresponding Kautz digraph \(\overrightarrow{K^3_k}\). The cycle \(\overrightarrow{C_7}\) in \(\overrightarrow{K^3_k}\) consists of red edges.
We can utilize Theorem 3.1 to obtain the locating coloring of \(C_n + K_m\) or \(C_n + \overline{K_m}\) in general.
Proposition 3.2. We have \(\chi_L(C_n + K_m) = \chi_L(C_n + K_1) + m-1 = \chi_L(C_n + \overrightarrow{K_m})\).
Next, another result can be obtained by replacing the wheel graph \(W_n\) with a disjoint union of cycles \(\cup_{i=1}^p C_{n_i} + K_m\) for some positive integers \(m \ge 1, n_i \ge 3, i \in [1,p]\). Several cycles in \(\cup_{i=1}^p C_{n_i}\) induce several directed disjoint union of cycles in Kautz digraph \(\overrightarrow{K^3_k}\).
Theorem 3.3. Let \(p\) be a positive integer and \(n_i \ge 3, i \in [1,p]\). It holds that \[\begin{aligned} \chi_L(\cup_{i=1}^p C_{n_i} + K_m) \le k+m , \end{aligned}\] if and only if there exists some directed cycles \(\cup_{i=1}^p \overrightarrow{C_{n_i}} \subseteq \overrightarrow{K^3_k}\) such that the subgraph \(\cup_{i=1}^p \overrightarrow{C_{n_i}}\) contains at most one vertex in each partition \(\pi(\overrightarrow{K^3_k})\).
Proof. Let \(G \cong \cup_{i=1}^p C_{n_i} + K_m\) be a graph with the vertex set \[\begin{aligned} V(G) = \{v_{i,j},u_l \ | \ i \in [1,p], j \in [1,n_i], l \in [1,m]\}, \end{aligned}\] and the edge set \[\begin{aligned} E(G) = \{v_{i,j}v_{i,j+1}, v_{i,j}u_l \ | \ i \in [1,p], j \in [1,n_i], l \in [1,m]\}, \end{aligned}\] with the index \(j\) is taken modulo \(n_i\). For the forward direction, let \(G\) have a locating coloring \(\alpha : V(G) \to \mathbb{Z}\) with \(k+m\) colors such that \(c_{\Pi}(x) \ne c_{\Pi}(y)\) for every \(x,y \in V(G)\). Let \(a_{i,j} = \alpha(v_{i,j})\alpha(v_{i,j+1})\alpha(v_{i,j+2})\) and \(a'_{i,j} = \alpha(v_{i,j+2})\alpha(v_{i,j+1})\alpha(v_{i,j})\). Construct a digraph \(\overrightarrow{H}\) with a vertex set \[\begin{aligned} V(\overrightarrow{H_i}) = \{a_{i,j} \ | \ j \in [1,n_i]\}, \end{aligned}\] and an arc set \[\begin{aligned} A(\overrightarrow{H_i}) = \{(a_{i,j},a_{i,j+1}) \ | \ j \in [1,n_i]\}, \end{aligned}\] with the index \(j\) is taken modulo \(n_i\). If there exist \(i_1,i_2 \in [1,p], j_1 \in [1,n_{i_1}], j_2 \in [1,n_{i_2}]\) where \((i_1,j_1) \ne (i_2,j_2)\) and \(a_{i_1,j_1} = a_{i_2,j_2}\) (or \(a_{i_1,j_1} = a'_{i_2,j_2}\)), then \(c_{\Pi}(a_{i_1,j_1}) = c_{\Pi}(a_{i_2,j_2})\). Since \(\alpha\) is a locating coloring, we have \(a_{i_1,j_1} \ne a_{i_2,j_2}\) and \(a_{i_1,j_1} \ne a'_{i_2,j_2}\) for every \(i_1,i_2 \in [1,p], j_1 \in [1,n_{i_1}], j_2 \in [1,n_{i_2}]\). Observe that if \(a_{i,j} \in V(\overrightarrow{H})\), then \(a_{i,j} \in V(\overrightarrow{K^3_k})\) and \(a_{i,j}\) is a unique vertex in the class partition \(\pi(\overrightarrow{K^3_k})\). Hence, \(\overrightarrow{H} = \cup_{i=1}^p \overrightarrow{H_i} \subseteq \overrightarrow{K^3_k}\) and \(\overrightarrow{H}\) is isomorphic to \(\cup_{i=1}^p \overrightarrow{C_{n_i}}\) which contains at most one vertex in each class partition \(\pi(\overrightarrow{K^3_k})\).
For the backward direction, let \(\overrightarrow{H}\) be a subgraph of \(\overrightarrow{K^3_k}\) which is isomorphic to a disjoint union of cycles \(\overrightarrow{C_{n_i}}\) which contains at most one vertex in each class partition \(\pi(\overrightarrow{K^3_k})\). We can write \(\overrightarrow{H} = \cup_{i=1}^p \overrightarrow{H_i}\) where \(H_i \cong C_{n_i}\) for every \(i \in [1,p]\). Let \(s_{i,1}s_{i,2}s_{i,3}\) be a vertex of \(\overrightarrow{H_i} \subseteq \overrightarrow{K^3_3}\). By the definition of the Kautz digraph, for every \(j \in [1,n_i]\) where \(s_{i,j},s_{i,j+1},s_{i,j+2} \in V(\overrightarrow{H_i})\) and \((s_{i,j}s_{i,j+1}s_{i,j+2},x) \in A(\overrightarrow{H_i})\), we obtain that \(x = s_{i,j+1}s_{i,j+2}s_{i,j+3}\) for some \(s_{i,j+3} \in [1,k]\). Hence, for every \(i \in [1,p]\), we have a cyclic sequence \(s_{i,1},s_{i,2},\ldots,s_{i,n_i}\) where \(s_{i,j} \in [1,k]\) for every \(j \in [1,n_i]\). From the fact that the subgraph \(\overrightarrow{H}\) contains at most one vertex in each class partition \(\pi(\overrightarrow{K^3_k})\), it holds that \[\begin{aligned} \label{res_disjoint_cycle}\begin{cases} (s_{i_1,j_1},s_{i_1,j_1+1},s_{i_1,j_1+2}) & \ne (s_{i_2,j_2},s_{i_2,j_2+1},s_{i_2,j_2+2}),\\ (s_{i_1,j_1},s_{i_1,j_1+1},s_{i_1,j_1+2}) & \ne (s_{i_2,j_2+2},s_{i_2,j_2+1},s_{i_2,j_2}),\end{cases} \end{aligned} \tag{2}\] for every \(i_1,i_2 \in [1,p], j_1 \in [1,n_{i_1}],j_2 \in [1,n_{i_2}]\). Define a coloring \(\alpha : V(G) \to \{1,2,…,k+m\}\) with \[\begin{aligned} \begin{cases} \alpha(v_{i,j}) = s_{i,j}, & \text{ for } i \in [1,p] \text{ and } j \in [1,n_i],\\ \alpha(u_l) = k + l, & \text{ for } l \in [1,m].\end{cases} \end{aligned}\]
The coloring \(\alpha\) induces a partition \(\Pi\). Clearly, \(c_{\Pi}(u_l)\) is unique for every \(l \in [1,m]\). For every pair of other vertices, from Eq. 2 it follows that \(c_{\Pi}(x) \ne c_{\Pi}(y)\) for every \(x,y \in V(G) \setminus \{u_l \mid l \in [1,m]\}\). Therefore, \(\chi_L(G) \le k+m.\) ◻
The next step of extension is to consider the circulant graphs instead of cycles. In simplest term, \(C_n(1) \cong C_n\). By considering \(C_n(1,2,…,t) + K_m\) for some positive integers \(t\) and \(m\), we need a distinct graph other than Kautz digraph \(\overrightarrow{K^{n+1}_k}\) for similar approach. Let \(Z^{2t+1}_k\) be a directed graph with the vertex set \[\begin{aligned} V(\overrightarrow{Z^{2t+1}_k}) = \{s_1s_2…s_{2t+1} \ | \ s_i \in [1,k], s_i \ne s_{i+j}, i \in [1,2t+1], j \in [1,t]\}, \end{aligned}\] with the index \(i\) is taken modulo \(2t+1\) and the arc set \[\begin{aligned} A(\overrightarrow{Z^{2t+1}_k}) = \{(s_1s_2…s_{2t+1},s_2s_3…s_{2t+2}) \ | \ s_i \in [1,k], s_i \ne s_{i+j}, j \in [1,t]\}. \end{aligned}\]
This graph has an order of \((k-t)^{t+1}P^k_t\) where \(P^k_t\) stands for a permutation of \(k\) elements into \(t\) positions. For \(t = 1\), it holds that \(\overrightarrow{Z^3_k} \cong \overrightarrow{K^3_k}\). Meanwhile, if \(t \ge 2\) then \(\overrightarrow{Z^{2t+1}_k} \subset \overrightarrow{K^{2t+1}_k}\). Let \(\pi(\overrightarrow{Z^3_k})\) be a partition of \(\overrightarrow{Z^3_k}\) such that two vertices \(r_1r_2…r_{2t+1}\) and \(s_1s_2…s_{2t+1}\) are in the same partition if \(r_{t+1} = s_{t+1}\) and \(\{s_1,s_2,…,s_{2t+1}\} = \{r_1,r_2,…,r_{2t+1}\}\). For example, the vertices \(23124\) and \(43124\) are contained in the same partition of \(Z^5_4\).
Theorem 3.4. Let \(n \ge 3\) be a positive integer and \(t \in [1,\lceil \frac{n}{2}\rceil]\). Then \[\begin{aligned} \chi_L(C_n(1,2,…,t) + K_m) \le k+m , \end{aligned}\] if and only if there exists a cycle \(\overrightarrow{C_n} \subseteq \overrightarrow{Z^{2t+1}_k}\) such that the subgraph \(\overrightarrow{C_n}\) contains at most one vertex in each partition \(\pi(\overrightarrow{Z^{2t+1}_k})\).
Proof. Let \(G \cong C_n(1,2,…,t) + K_m\). Recall that \(G\) as the graph with the vertex set \[\begin{aligned} V(G) = \{v_i,u_l \ | \ i \in [1,n], l \in [1,m]\}, \end{aligned}\] and the edge set \[\begin{aligned} E(G) = \{v_iv_{i+p}, v_iu_l \ | \ i \in [1,n], p \in [1,t], l \in [1,m]\}, \end{aligned}\] with the index \(i\) and \(p\) taken modulo \(n\). For the forward direction, let \(\alpha : V(G) \to \mathbb{Z}\) be a locating coloring of \(G\) with \(k+m\) colors such that \(c_{\Pi}(x) \ne c_{\Pi}(y)\) for every \(x,y \in V(G)\). Let \(a_i = \alpha(v_{i})\alpha(v_{i+1})…\alpha(v_{i+2t})\).Construct a digraph \(\overrightarrow{H}\) with the vertex set \[\begin{aligned} V(\overrightarrow{H}) = \{a_i \ | \ i \in [1,n]\}, \end{aligned}\] and the arc set \[\begin{aligned} A(\overrightarrow{H}) = \{(a_i,a_{i+1}) \ | \ i \in [1,n]\}, \end{aligned}\] with the index \(i\) taken modulo \(n\). If there exists \(\{r_1,r_2,\ldots,r_{2t+1} \mid r_i \in [1,k]\}\) such that \(r_{t+1} = \alpha(v_{i+t})\) and \(\{r_1,r_2,\ldots,r_{2t+1}\} = \{\alpha(v_i),\alpha(v_{i+1}),\ldots,\alpha(v_{i+2t})\}\), then \(c_{\Pi}(a_i) = c_{\Pi}(x)\) for some ordering \(x\) of \(\{r_1 r_2 \ldots r_{2t+1}\}\) where the \((i+1)\)-term is \(r_{t+1}\). Since \(\alpha\) is a locating coloring, for every \(i \in [1,n]\), \(\alpha(v_{i+t}) \ne r_{t+1}\) or \[\begin{aligned} \{r_1,r_2,\ldots,r_{2t+1}\} \ne \{\alpha(v_i),\alpha(v_{i+1}),\ldots,\alpha(v_{i+2t})\}, \end{aligned}\] for every \(r_1 r_2 \ldots r_{2t+1} = x \in V(\overrightarrow{H})\) where \(x \ne a_i\). It follows that if \(a_i \in V(\overrightarrow{H})\), then \(a_i \in V(Z^{2t+1}_k)\) and \(a_i\) is a unique vertex in the class partition \(\pi(\overrightarrow{Z^{2t+1}_k})\). Then, \(\overrightarrow{H}\) is a subgraph of \(\overrightarrow{Z^{2t+1}_k}\) which is isomorphic to a cycle \(\overrightarrow{C_n}\) containing at most one vertex in each class partition.
For the backward direction, let \(\overrightarrow{H} \subseteq \overrightarrow{Z^{2t+1}_k}\) which is isomorphic to a cycle \(\overrightarrow{C_n}\) containing at most one vertex in each class partition. Let \(s_1 s_2 \ldots s_{2t+1}\) be a vertex of \(\overrightarrow{H} \subseteq \overrightarrow{Z^{2t+1}_k}\). By the definition of \(Z^{2t+1}_k\) as a subgraph of Kautz digraph, for every \(i \in [1,n]\) where \(s_1 s_2 \ldots s_{2t+1} \in V(\overrightarrow{H})\) and \((s_1 s_2 \ldots s_{2t+1},x) \in A(\overrightarrow{H})\), then \(x = s_2 s_3 \ldots s_{2t+2}\) for some \(s_{2t+2} \in [1,k]\). Observe that we have a cyclic sequence \(s_1 s_2 \ldots s_n\) where \(s_i \in [1,k]\) for every \(i \in [1,n]\). Since \(\overrightarrow{H}\) contains at most one vertex in each class partition \(\pi(\overrightarrow{Z^{2t+1}_k})\), whenever \(s_i = s_j\) it follows that \[\begin{aligned} \label{res_circulant} \{s_{i+p} \ | \ p \in [-t,t]\} & \ne \{s_{j+p} \ | \ p \in [-t,t]\}. \end{aligned} \tag{3}\]
Let \(\alpha : V(G) \to \{1,2,…,k+m\}\) be a coloring with \[\begin{aligned} \begin{cases} \alpha(v_i) = s_i, & \text{ for } i \in [1,n],\\ \alpha(u_l) = k + l, & \text{ for } l \in [1,m].\end{cases} \end{aligned}\]
This coloring \(\alpha\) induces a partition \(\Pi\). Obviously, \(c_{\Pi}(u_l)\) is unique for every \(l \in [1,m]\). Moreover, by Eq. 3, \(c_{\Pi}(v_i) \ne c_{\Pi}(v_j)\) for every distinct \(i,j \in [1,n]\). Henceforth, \(\chi_L(C_n(1,2,…,t) + K_m) \le k+m.\) ◻
Remark 3.5. The result in Theorem 3.3 and Theorem 3.4 also holds if we replace \(K_m\) with \(\overline{K_m}\).
In this section, we attempt to determine \(\chi_L(C_n(1,2,3) + K_m)\) and \(\chi_L(C_n(1,2) + K_m)\) by creating algorithms which are based on Theorem 3.4. This algorithm is described as follows:
For given \(n\) and \(t\), this algorithm eventually terminates since the locating chromatic number is upper bounded. Using this algorithm, we are able to determine the locating chromatic number of \(\chi_L(C_n(1,2,3) + K_m)\) with \(n \in [8,24]\) and \(\chi_L(C_n(1,2) + K_m)\) with \(n \in [6,28]\). The result is presented in Table 1 and Table 2. We also provide the locating coloring given in a sequence of colors of vertices on outer vertices. An example of locating chromatic coloring of \(C_{12}(1,2) + K_1\) is given in Figure 3. Based on the table, we have the summary in Theorem 4.1 and 4.2.
| \(n\) | \(\chi_L(G)\) | Coloring on the outer vertices |
|---|---|---|
| \(8\) | \(m+8\) | \([1, 2, 3, 4, 5, 6, 7, 8]\) |
| \(9\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 5, 3, 6]\) |
| \(10\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 5, 6]\) |
| \(11\) | \(m+7\) | \([1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 7]\) |
| \(12\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 6]\) |
| \(13\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 6]\) |
| \(14\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 4, 6]\) |
| \(15\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 6]\) |
| \(16\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 2, 4, 6]\) |
| \(17\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 2, 5, 3, 6]\) |
| \(18\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 6, 5, 3, 4, 6]\) |
| \(19\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 4, 6, 5, 2, 3, 6]\) |
| \(20\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 2, 4, 6, 1, 2, 4, 6]\) |
| \(21\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 2, 4, 6, 1, 5, 2, 4, 6]\) |
| \(22\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 2, 4, 6, 3, 5, 1, 2, 3, 6]\) |
| \(23\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 2, 5, 3, 1, 6, 2, 3, 5, 4, 6]\) |
| \(24\) | \(m+6\) | \([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 2, 4, 6, 1, 2, 5, 6, 1, 2, 3, 6]\) |
Theorem 4.1. Let \(n \in [8,24]\). Then \[\begin{aligned} \chi_L(C_n(1,2,3) + K_m) = \begin{cases} m + 8, & \text{if } n = 8,\\ m + 7, & \text{if } n = 11,\\ m + 6, & \text{if } n \in [9,24] \setminus \{11\}. \end{cases} \end{aligned}\]
Theorem 4.2. Let \(n \in [6,28]\). Then \[\begin{aligned} \chi_L(C_n(1,2) + K_m) = \begin{cases} m + 6, & \text{if } n = 6,\\ m + 5, & \text{if } n \in [7,28]. \end{cases} \end{aligned}\]
Remark 4.3. The result in Theorem 4.1 and Theorem 4.2 also holds if we replace \(K_m\) with \(\overline{K_m}\).
| \(n\) | \(\chi_L(G)\) | Coloring on the outer vertices |
|---|---|---|
| \(6\) | \(m+6\) | \([1, 2, 3, 4, 5, 6]\) |
| \(7\) | \(m+5\) | \([1, 2, 3, 1, 2, 4, 5]\) |
| \(8\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 4, 5]\) |
| \(9\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 4, 2, 5]\) |
| \(10\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 5]\) |
| \(11\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 3, 5]\) |
| \(12\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5]\) |
| \(13\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 4, 2, 5]\) |
| \(14\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 3, 4, 2, 3, 5]\) |
| \(15\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 5]\) |
| \(16\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 4, 3, 5]\) |
| \(17\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5]\) |
| \(18\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 5, 4, 2, 5]\) |
| \(19\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 5, 1, 2, 5]\) |
| \(20\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 1, 2, 5]\) |
| \(21\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 3, 4, 2, 5]\) |
| \(22\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 5, 1, 4, 5, 1, 2, 5]\) |
| \(23\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 3, 4, 5, 1, 2, 5]\) |
| \(24\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 1, 4, 2, 5, 4, 3, 5]\) |
| \(25\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 4, 1, 2, 5, 4, 3, 2, 5]\) |
| \(26\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 1, 2, 5, 4, 3, 5, 1, 3, 5]\) |
| \(27\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 1, 4, 2, 5, 4, 2, 5, 4, 3, 5]\) |
| \(28\) | \(m+5\) | \([1, 2, 3, 1, 2, 3, 1, 4, 2, 1, 3, 5, 1, 3, 4, 2, 5, 1, 2, 4, 5, 2, 4, 3, 5, 4, 3, 5]\) |
This research has been supported by the Ministry of Higher Education, Sciences, and Technology, Indonesia under the scheme of “Penelitian Fundamental Regular”. We are also grateful for the feedback from the anonymous referees.