1 Introduction
The topic of locating-chromatic number was introduced by Chartrand, et al. [1] in 2002. They determined the locating-chromatic numbers of paths, cycles, and double stars. Inspired by Chartrand, et al., other authors have determined the locating-chromatic numbers of some well known classes of graphs, i.e. amalgamation of stars and firecrackers by Asmiati, et al. [2,3], Kneser graphs by Behtoei and Omoomi [4], Halin graphs by Purwasih, et al. [5], Cartesian product of graphs and joint product graphs by Behtoei and Omoomi [6] and Behtoei [7], and homogeneous lobster graphs by Syofyan, et al. [8].
Let ܩ ൌ ሺܸ, ܧሻ be a connected graph. We define the distance as the minimum length of path connecting vertices ݑ and ݒ in ܩ, denoted by ݀ሺݑ, ݒሻ. A ݇ coloring of ܩ is a function ܿ: ܸሺܩሻ → ሼ1,2, … , ݇ሽ where ܿሺݑሻ ് ܿሺݒሻ for any two adjacent vertices ݑ and ݒ in ܩ. Thus, the coloring ܿ induces a partition Π of ܸሺܩሻ into ݇ color classes (independent sets) ܥଵ, ܥଶ,…,ܥ where ܥ is the set of all vertices colored by ݅ for 1 ݅ ݇. The color code ܿஈሺݒሻ of a vertex ݒ in ܩ is defined as the ݇-vector ሺ݀ሺݒ, ܥଵሻ, ݀ሺݒ, ܥଶሻ, … , ݀ሺݒ, ܥሻሻ where ݀ሺݒ, ܥሻ ൌ minሼ݀ሺݒ, ݔሻ | ݔ ∋ ܥሽ for 1݅݇. The ݇ െcoloring ܿ of ܩ such that all
Received June 10th, 2015, 1st Revision September 9th, 2015, 2nd Revision October 28th, 2015, Accepted for publication November 15th, 2015.
Copyright © 2016 Published by ITB Journal Publisher, ISSN: 2337-5760, DOI: 10.5614/j.math.fund.sci.2016.48.1.4
vertices have different color codes is called a locating coloring of G. The least integer k is such that there is a locating coloring in G that is called the locating-chromatic number of G, denoted by \(\chi_L(G)\).
Chartrand, et al. in [1] have determined all graphs of order n with locating-chromatic number n, namely a complete multipartite graph of n vertices. Furthermore in Chatrand, et al. [9], all graphs of order n with locating-chromatic number n-1 were characterized. Chartrand, et al. [1] also proved that there exists a tree of order n, \(n \ge 5\), having locating-chromatic number k if and only if \(k \in \{3,4,...,n-2,n\}\). Recently, Baskoro and Asmiati [10] have characterized all trees with locating-chromatic number 3. In this investigation, we have characterized all trees of order n with locating-chromatic number n-t, for any integers n and t, where n > t+3 and \(1 \le t < \frac{n}{2}\).
The following results were proved in Chartrand, et al. [1].
Lemma 1. Let G be a simple, connected and non directed graph. Let function c be a locating coloring of G and \(u, v \in V(G)\). If d(u, w) = d(v, w) for every \(w \in V(G) \setminus \{u, v\}\), then \(c(u) \neq c(v)\).
Corollary 1. If G is a connected graph containing a vertex that is adjacent to k leaves of G, then \(\chi_L(G) \ge k + 1\).
2 Main Results
In the following theorem, we provide a method to construct a tree T of order n from any tree of smaller order t+1 where n>5 and \(2 \le t < \frac{n}{2}\), such that \(\chi_L(T)=n-t\). A vertex v of degree \(\ge 2\) in a tree T is called a stem if it is adjacent to a leaf.
Theorem 1. For any integer n and t, where n > t+3 and \(2 \le t < \frac{n}{2}\), let \(T_{t+1}\) be any tree of order t+1. Let \(T_n\) be a tree of order n obtained by joining n-t-1 new vertices to a vertex \(x \in V(T_{t+1})\), where x is not a stem. Then, \(\chi_L(T_n) = n-t\).
Proof. Let \(V(T_n) = \{x, y_i, z_j | 1 \le i \le n - t - 1, 1 \le j \le t\}\), where x is adjacent to n - t - 1 leaves, \(y_i\) are the leaves adjacent to x, and \(z_j\) are other vertices in \(T_n\). Define a (n - t) -coloring \(c: V(T_n) \to \{1, 2, ..., n - t\}\) as follows:
1. \[c(x) = n - t\],
- 2. \(c(y_i) = i\) for \(1 \le i \le n t 1\),
- 3. \(c(z_i) = j\) for \(1 \le j \le t\).
Next, we show that the color codes of all vertices under the coloring c are distinct. We only consider pairs of vertices with the same color. The possibilities are for the pairs of vertices \(y_i\) and \(z_j\) for some i,j. If \(z_j\) is adjacent to x, then \(c_{\Pi}(y_i) \neq c_{\Pi}(z_j)\) because \(c_{\Pi}(y_i)\) contains exactly one entry 1, while \(c_{\Pi}(z_j)\) contains at least two entries 1. If \(z_j\) is not adjacent to x then \(c_{\Pi}(y_i) \neq c_{\Pi}(z_j)\) because \(c_{\Pi}(y_i)\) contains entry 1 in the \((n-t)^{th}\) ordinate, while \(c_{\Pi}(z_j)\) does not contain entry 1 in the \((n-t)^{th}\) ordinate. Since every vertex of \(T_n\) has distinct color codes, c is a locating coloring of \(T_n\). So, \(\chi_L(T_n) \leq n-t\).
Now, since \(T_n\) contains a vertex x that is adjacent to n-t-1 leaves, then by Corollary \(1, \chi_L(T_n) \ge n-t\). Hence, \(\chi_L(T_n) = n-t\). \(\square\)
In the following theorem, we give a necessary condition of a tree of order n whose locating-chromatic number is n-t, where \(2 \le t < \frac{n}{2}\).
Theorem 2. For any integer n and t, where n > t + 3 and \(2 \le t < \frac{n}{2}\), let \(T_n\) be a tree of order n. If \(\chi_L(T_n) = n - t\), then \(T_n\) has exactly one stem with n - t - 1 leaves.
Proof. Since \(\chi_L(T_n) = n - t\), every stem of \(T_n\) is adjacent to at most n - t - 1 leaves. Suppose that there is no stem of \(T_n\) having n - t - 1 leaves. Then every stem of \(T_n\) is adjacent to at most n - t - 2 leaves. Furthermore, we have a locating coloring for \(T_n\) by using n - t - 1 colors as follows.
Let there be b stems in \(T_n\). First, we denote all stems of \(T_n\) by \(s_i\), for \(1 \le i \le b\), the leaves of \(T_n\) adjacent to \(s_i\) by \(l_{ij}\), for \(1 \le i \le b\) and \(1 \le j \le n-t-2\), and the remaining vertices by \(v_k\), for \(0 \le k \le n-4\). Let \(N(s_i)\) be the set of neighbors of \(s_i\), for \(1 \le i \le b\). For a coloring c of \(V(T_n)\), define \(c(N(s_i)) = \{c(x)|x \in N(s_i)\}\). Now, define a (n-t-1)-coloring c of \(T_n\) with the following steps:
- 1. For all stems \(s_i\), define \(c(s_i) = 1\) or 2 such that if there are at least two stems adjacent to the same \(v_k\) for some k, then two of these stems receive different colors.
- 2. For all vertices \(v_k\) adjacent to a stem, assign \(c(v_k) = a\), for some \(a \in \{3,4,5,...,n-t-1\}\) such that \(c(v_k) \neq c(v_l)\) for \(k \neq l\).
- 3. For all vertices ݒ not adjacent to a stem, define ܿሺݒሻൌܽ, for some ܽ ∈ ሼ3,4,5, … , ݊ െ ݐ െ 1ሽ such that ܿሺݒሻ ് ܿሺݒሻ if ݀ሺݒ, ܥሻ ൌ ݀ሺݒ, ܥሻ for ݅ ൌ 1, 2.
- 4. For all leaves ݈, define ܿሺ݈ሻൌܽ, for some ܽ ∈ ሼ1,2, … , ݊ െ ݐ െ 1ሽ such that all vertices (including leaves) adjacent to stems ݏ and ݏ satisfy ܿሺܰሺݏሻሻ ് ܿሺܰሺݏሻሻ for any ്݅.
Figure 1 Trees ܪଵ, ܪଶ, ܪଷ, ܪସ, ܪହ, ܪ.
Observe that, with the exception of the six trees depicted in Figure 1, the coloring ܿ can always be done for any tree ܶ, ݊6. Meanwhile, for all trees in Figure 1 we cannot use the coloring ܿ because the number of colors is smaller than the number of vertices ݒ adjacent to a stem. However, we can define another coloring for ܶ in Figure 1 by ݊െݐെ1 colors such that if ݊ ൌ 8, 9, 10, 11, 13 then ݐ ൌ 3, 4, 4, 5, 6, respectively.
Next, we show that ܿ is a locating coloring of ܶ. Let ݔ and ݕ be two vertices of ܶ such that ܿሺݔሻ ൌ ܿሺݕሻ. We distinguish five cases:
Case 1. ݔൌݏ and ݕൌݏ, for ്݆݅.
Since ܿሺܰሺݏሻሻ ് ܿሺܰሺݏሻሻ for ്݆݅ (from Step (4)), we obtain that
ܿஈሺݔሻ ് ܿஈሺݕሻ.
Case 2. ݔൌݒ and ݕൌݒ, for ്݈݇.
If \(v_k\) is adjacent to a stem \(s_i\) and \(v_l\) is not adjacent to any stem, then \(c_{\Pi}(v_k) \neq c_{\Pi}(v_l)\) because \(c_{\Pi}(v_k)\) contains entry 1 in the first or second ordinate, while \(c_{\Pi}(v_l)\) does not contain entry 1 in the first and second ordinate (from Step (1), (2) and (3)).
Case 3. \(x = l_{ij}\) and \(y = l_{pq}\), for \(i \neq p\).
Since \(c(N(s_i)) \neq c(N(s_p))\) for \(i \neq p\) (from step (4)), we obtain that \(c_{\Pi}(x) \neq c_{\Pi}(y)\).
Case 4. \(x = s_i\) and \(y = l_{pq}\).
Since \(c(N(s_i)) \neq c(N(s_p))\) for \(i \neq p\) (from step (4)), we obtain that \(c_{\Pi}(x) \neq c_{\Pi}(y)\).
Case 5. \(x = v_k\) and \(y = l_{ij}\).
Then there are two possibilities for this case:
- i) If \(v_k\) is adjacent to a stem, then \(c_{\Pi}(v_k) \neq c_{\Pi}(l_{ij})\) because \(c_{\Pi}(v_k)\) contains at least two entries 1, while \(c_{\Pi}(l_{ij})\) contains exactly one entry 1 (from Step (1),(2),(4)).
- ii) If \(v_k\) is not adjacent to any stem, then \(c_{\Pi}(v_k) \neq c_{\Pi}(l_{ij})\) because \(c_{\Pi}(v_k)\) does not contain entry 1 in the first and second ordinate, while \(c_{\Pi}(l_{ij})\) contains entry 1 in the first or second ordinate (from Step (1),(3),(4)).
By the above cases, we prove that c is a locating coloring of \(T_n\). Then \(\chi_L(T_n) \le n - t - 1\), which contradicts \(\chi_L(T_n) = n - t\). Hence, there is a stem of T having n - t - 1 leaves.
Next, we will show that there is only one stem of \(T_n\) having n-t-1 leaves. We suppose that there are two stems of \(T_n\) adjacent to n-t-1 leaves. Then, \(|V(T_n)| \geq 2(n-t)\). Since \(t < \frac{n}{2}\), \(|V(T_n)| \geq 2(n-t) > n\), a contradiction with \(|V(T_n)| = n\). \(\square\)
Applying Theorem 1 and Theorem 2, we obtain the following theorem.
Theorem 3. For any integer n and t, where n > t + 3 and \(2 \le t < \frac{n}{2}\), let \(T_n\) be a tree of order n. Then \(\chi_L(T_n) = n - t\) if and only if \(T_n\) has exactly one stem with n - t - 1 leaves.
Based on Theorem 3, we can determine all trees \(T_n\) on n vertices with \(\chi_L(T_n) = n - t\) for any integers n and t, where n > t + 3 and \(2 \le t < \frac{n}{2}\). In particular, if t = 2, 3, or 4, all trees \(T_n\) with \(\chi_L(T_n) = n - t\) are the caterpillars shown in Figures 2, 3, and 4. But for \(t \ge 5\), there are trees \(T_n\) on n vertices other than caterpillars with \(\chi_L(T_n) = n - t\), for example the cases of t = 5 and 6, all trees with \(\chi_L(T_n) = n - 5\) and \(\chi_L(T_n) = n - 6\) are depicted in Figure 5 and Figure 6, respectively. Therefore, as a special case of Theorem 3, we have the following corollary.
First, we give the definition of a caterpillar. Let \(P_m = x_1 x_2 \dots x_m\) be a path with m vertices. A caterpillar \(C(m; n_1, n_2, \dots, n_m)\), is obtained by joining \(n_i\) new vertices to every vertex \(x_i\) in a path \(P_m\), \(n_i \ge 0\), \(1 \le i \le m\).
Corollary 2. For any integer n and t, where n > t + 3 and t = 2,3,4, let \(T_n\) be a tree of order n. Then \(\chi_L(T_n) = n - t\) if and only if \(T_n\) is a caterpillar \(C(m; n_1, n_2, ..., n_m)\) where \(0 \le n_i \le n - t - 1\), \(2 \le m \le t\), \(n_1, n_m \ne 0\), and exactly one of \(n_i\) is equal to n - t - 1.
All caterpillars in the Corollary 2 are shown in Figure 2, 3, and 4.
Figure 2 All trees of order n > 5 with locating chromatic number n - 2.
Figure 3 All trees of order n > 6 with locating chromatic number n - 3.
Figure 4 All trees of order n > 7 with locating chromatic number n - 4.
Figure 4 (continued) All trees of order ૠ with locating chromatic number .െ
Figure 5 All trees of order ૡ with locating chromatic number െ.
Figure 6 All trees of order ૢ with locating chromatic number െ.
Acknowledgements
This research was supported by Research Grant Program Riset Unggulan ITB-DIKTI, Ministry of Research, Technology and Higher Education, Indonesia.