1 Introduction
Let G be a finite, simple, and connected graph. Let c be a proper coloring of a connected graph G using the colors 1,2,...,k for some positive integer k, where \(c(u) \neq c(v)\) for adjacent vertices u and v in G. Thus, the coloring c can be considered as a partition \(\prod\) of V(G) into color classes (independent sets) \(C_1, C_2,..., C_k\), where the vertices of \(C_i\) are colored by i for \(1 \leq i \leq k\). The color code \(c_{\prod}(v)\) of a vertex v in G is the ordered k-tuple \((d(v,C_1),...,d(v,C_k))\) where \(d(v,C_i)=\min\{d(v,x)|x\in C_i\}\) for \(1\leq i\leq k\). If all distinct vertices of G have distinct color codes, then c is called a locating-coloring of G. A minimum locating-coloring uses a minimum number of colors and this number is called the locating-chromatic number of graph G, denoted by \(\chi_L(G)\).
*Permanent address: Mathematics Departement, Faculty of Mathematics and Natural Sciences, Universitas Lampung, Jl. Brojonegoro no.1 Bandar Lampung, Lampung. Received January 11<sup>th</sup>, 2010, Revised July 14<sup>th</sup>,2010, Accepted for publication July 28<sup>th</sup>, 2010.
The following definition of an amalgamation of graphs is taken from [3]. For i=1,2,...,k, let \(G_i\) be a graph with a fixed vertex \(v_{oi}\). The amalgamation Amal\((G_i,v_{oi})\) is a graph formed by taking all the \(G_i\)'s and identifying their fixed vertices. In this paper, we consider the amalgamation of stars. More precisely, for i=1,2,...,k, let \(G_i=K_{1,n_i},n_i\geq 1\) where \(v_{oi}\) be any leaf (a vertex of degree 1) of \(K_{1,n}\). We denote the amalgamation of k stars \(K_{1,n}\) by
\(S_{k,(n_1,n_2,\dots,n_k)}\), \(k \ge 2\). We call the identified vertex as the center (denoted by x), the vertices of distance 1 from the center as the intermediate vertices (denoted by \(l_i\); \(i=1,2,\dots,k\)), and the j-th leaf of the intermediate vertex \(l_i\) by \(l_{ij}\) (\(j=1,2,\dots,m-1\)). In particular, when \(n_i=m\), \(m\ge 1\) for all i, we denote the amalgamation of k isomorphic stars \(K_{1,m}\) by \(S_{k,m}\).
The locating-chromatic number was firstly studied by Chartrand et al. [1]. They determined the locating-chromatic numbers of some well-known classes such as paths, cycles, complete multipartit graphs and double stars. Apart of paths and double stars, the locating-chromatic number of other trees are also considered by Chartrand et al. [2]. They constructed a tree of order \(n \ge 5\) with the locating-chromatic number k, where \(k \in \{3,4,...,n-2,n\}\). They also showed that no tree on n vertices with locating-chromatic number n-1.
Based on the previous results, locating-chromatic number of amalgamation of stars have not been studied. Motivated by this, in this paper we determine the locating-chromatic number of amalgamation of stars.
Beside that, we also discuss the monotonicity property of the locating-chromatic number for the class of amalgamation of stars. Clearly, the locating-chromatic number of a star \(K_{1,n}\) is n+1, for any n (since all vertices must have
different color codes). Since any connected subgraph H of \(K_{1,n}\) is also a star with small size, then we clearly have \(\chi_L(H) \leq \chi_L(K_{1,n})\). However in general for any connected subgraph \(H \subseteq G\), the locating-chromatic number of H may not be necessarily smaller or equal to the locating-chromatic number of G.
In this paper, we also investigate the monotonicity property of the locating-chromatic number for amalgamation of stars, \(S_{k,m}\). We derive a sufficient condition for a connected subgraph \(H \subseteq S_{k,m}\) satisfying \(\chi_L(H) \le \chi_L(S_{k,m})\).
The following results were proved by Chartrand et al. in [1]. The set of neighbours of a vertex v in G is denoted by N(v).
Theorem 1.1. Let c be a locating-coloring in a connected graph G. If u and v are distinct vertices of G such that d(u,w) = d(v,w) for all \(w \in V(G) - \{u,v\}\), then \(c(u) \neq c(v)\). In particular, if u and v are non adjacent vertices of G such that N(u) = N(v), then \(c(u) \neq c(v)\).
Corollary 1.1. If G is a connected graph containing a vertex adjacent to k leaves of G, then \(\chi_L(G) \ge k + 1\).
2 Main Results
We first prove some lemmas regarding the properties of locating-chromatic number of amalgamation of stars. From now on \(S_{k,m}\) denotes the amalgamation of k isomorphic stars \(K_{1,m}\).
Lemma 2.1. For \(k \ge 2\), \(m \ge 2\), let c be a proper coloring of \(S_{k,m}\), using at least m colors. The coloring c is a locating-coloring if and only if \(c(l_i) = c(l_n)\), \(i \ne n\) implies \(\{c(l_{ij}) | j = 1, 2, ..., m-1\}\) and \(\{c(l_{nj}) | j = 1, 2, ..., m-1\}\) are distinct.
Proof. Let \(P = \{c(l_{ij}) \mid j = 1, 2, ..., m-1\}\) and \(Q = \{c(l_{nj}) \mid j = 1, 2, ..., m-1\}\). Let c be a locating-coloring of \(S_{k,m}\), \(k \geq 2, m \geq 2\) using at least m colors and \(c(l_i) = c(l_n)\), for some \(i \neq n\). Suppose that P = Q. Because \(d(l_i, u) = d(l_n, u)\) for every \(u \in V \setminus \left\{\{l_{ij} \mid j = 1, 2, ..., m-1\} \cup \{l_{nj} \mid j = 1, 2, ..., m-1\}\right\}\) then the color codes of \(l_i\) and \(l_n\) will be the same. So c is not a locating-coloring, a contradiction. Therefore \(P \neq Q\).
Let \(\Pi\) be a partition of V(G) into color classes with \(|\Pi| \ge m\). Consider \(c(l_i) = c(l_n), i \ne n\). Since \(P \ne Q\), there are color x and color y such that \((x \in P, x \notin Q)\) and \((y \in P, y \notin Q)\). We will show that color codes for every \(v \in V(S_{k,m})\) is unique.
• Clearly, \(c_{\Pi}(l_i) \neq c_{\Pi}(l_n)\) because their color codes differ in the xth-ordinate and yth-ordinate.
• If \(c(l_{ij}) = c(l_{ns})\), for some \(l_i \neq l_n\), we will show that \(c_{\Pi}(l_{ij}) \neq c_{\Pi}(l_{ns})\). We divide into two cases.
Case 1. If \(c(l_i) = c(l_n)\) then by the premise of this theorem, \(P \neq Q\). So \(c_{\prod}(l_{ii}) \neq c_{\prod}(l_{ns})\).
Case 2. Let \(c(l_i) = r_1\) and \(c(l_n) = r_2\), with \(r_1 \neq r_2\). Then \(c_{\Pi}(l_{ij}) \neq c_{\Pi}(l_{ns})\) because their color codes are different at least in the \(r_1\) th-ordinate and \(r_2\) th-ordinate.
- If \(c(l_i) = c(l_{nj})\), \(l_i \neq l_n\), then \(c_{\Pi}(l_i)\) contains at least two components of value 1, whereas \(c_{\Pi}(l_{nj})\) contains exactly one component of value 1. Thus \(c_{\Pi}(l_i) \neq c_{\Pi}(l_{nj})\).
- If \(c(x) = c(l_{ij})\), then color code of \(c_{\Pi}(x)\) contains at least two components of value 1, whereas \(c_{\Pi}(l_{ij})\) contains exactly one component of value 1. Thus \(c_{\Pi}(x) \neq c_{\Pi}(l_{ij})\).
From all above cases, we see that the color code for each vertex in \(S_{k,m}\) is unique, thus c is a locating-coloring. \(\square\)
Lemma 2.2. Let c be a locating coloring of \(S_{k,m}\) using m+a colors and \(H(a) = (m+a-1)\binom{m+a-1}{m-1}\), \(a \ge 0\). Then \(k \le H(a)\).
Proof. Let c be a locating-coloring of \(S_{k,m}\) using m+a colors. For fixed i, let \(c(l_i)\) be a color of intermediate vertex \(l_i\), then the number color combinations can be used by \(\{l_{ij} \mid j=1,2,...,m-1\}\) is \(\binom{m+a-1}{m-1}\). Because one color is used for coloring the center x, there are (m+a-1) colors for \(l_i\), for every i=1,2,...,k. By Lemma 2.1, the maximum number of k is \((m+a-1)\binom{m+a-1}{m-1}=H(a)\). So \(k\leq H(a)\). \(\square\)
The main result of this paper concerns about locating-chromatic number of \(S_{k,m}\).
Theorem 2.1. For \(a \ge 0\), \(k \ge 2\), \(m \ge 2\), let \(H(a) = (m+a-1) \binom{m+a-1}{m-1}\). Then,
\[\chi_L(S_{k,m}) = \begin{cases} m & \text{for} \qquad 2 \le k \le H(0), \ m \ge 3, \\ m+a & \text{for} \qquad H(a-1) < k \le H(a), \ a \ge 1. \end{cases}\]
Proof. First, we determine the trivial lower bound. By Corollary 1.1, each vertex \(l_i\) is adjacent to (m-1) leaves, for i=1,2,...,k. Thus, \(\chi_L(S_{k,m}) \ge m\).
Next, we determine the upper bound of \(\chi_L(S_{k,m})\) for \(2 \le k \le H(0) = m-1\). Let c be a coloring of \(V(S_{k,m})\) using m colors. Without loss of generality, we can assign c(x) = 1 and \(c(l_i) = i+1\) for i = 1, 2, ..., k. To make sure that the leaves will have distinct color code, we assign \(\{l_{ij} \mid j = 1, 2, ..., m-1\}\) by \(\{1, 2, ..., m\} \setminus \{i+1\}\) for any i. Then, by Lemma 2.1, we have that c is a locating-coloring. Thus \(\chi_L(S_{k,m}) \le m\).
Next, we shall improve the lower bound for the case of k such that \(H(a-1) < k \le H(a), a \ge 1\). Since k > H(a-1) then by Lemma 2.2, \(\chi_L(S_{k,m}) \ge m+a\). On the other hand if k > H(a) then by Lemma 2.2, \(\chi_L(S_{k,m}) \ge m+a+1\). Thus \(\chi_L(S_{k,m}) \ge m+a\) if \(H(a-1) < k \le H(a)\).
Next, we determine the upper bound of \(\chi_L(S_{k,m})\) for \(H(a-1) < k \le H(a)\), \(a \ge 1\). Without loss of generality, let c(x) = 1 and color the intermediate vertices \(l_i\) by 2,3,...,m+a in such a way that the number of the intermediate vertices receiving the same color t does not exceed \(\binom{m+a-1}{m-1}\), for any t. We are able to do so because \(H(a-1) < k \le H(a)\). Therefore, if \(c(l_i) = c(l_n)\), \(i \ne n\) then we can manage \(\{c(l_{ij}) | j = 1,2,...,m-1\} \ne \{c(l_{nj}) | j = 1,2,...,m-1\}\). By Lemma 2.1, c is a locating-coloring on \(S_{k,m}\). So \(\chi_L(S_{k,m}) \le m+a\) for \(H(a-1) < k \le H(a)\). \(\square\)
The following figures show minimum locating-colorings on \(S_{4,6}\) and \(S_{9,3}\) .
Figure 1 A minimum locating-coloring of \(S_{4,6}\).
Figure 2 A minimum locating-coloring of \(S_{9,3}\).
Next, we discuss the monotonicity property of locating-chromatic number for the amalgamation of stars.
Theorem 2.2 If \(2 \le k \le m-1\), then \(\chi_L(G) \le \chi_L(S_{k,m})\) for every \(G \subseteq S_{k,m}\) and \(G \ne K_{1,m}\).
Proof. Let c be a minimum locating-coloring of \(S_{k,m}\) obtained from Theorem 2.1. Let G be any connected subgraph of \(S_{k,m}\). Define a coloring c' on G by preserving colors used in \(S_{k,m}\) for the corresponding vertices, namely c'(v') = c(v) if v is the corresponding vertex of v' in \(S_{k,m}\). We show that c' is a locating-coloring of G.
If there exist \(l_i\), \(l_n\) such that \(\{c'(l_{ij}) | j=1,2,...,r\} = \{c'(l_{nj}) | j=1,2,...,r\}\), with \(1 \le r \le m-1\), then color codes of \(l_{ij}\) and \(l_{nj}\) for every j=1,2,3,...,m is unique because \(c'(l_i) \ne c'(l_n)\) for every \(l_i \ne l_n\). If \(c'(l_i) = c'(l_{nj}) \ne c'(x)\), then the first component of \(c'_{\pi}(l_i)\) has value 1, whereas for \(c'_{\pi}(l_{nj})\) it has value 2. So color code of \(l_i\) and \(l_{nj}\) are different. Next, if \(c'(x) = c'(l_{nj})\), \(G \ne P_3\) then their color codes are different because \(c'(l_i) \ne c'(l_n)\) for every \(l_i \ne l_n\). For the case \(G = P_3\), \(v_i \in V(P_3)\) for each i is colored by 1, 2, and 3 respectively. Because the color codes for every \(v \in V(G)\) is unique, then c' is a locating-coloring of G. So \(\chi_L(G) \le \chi_L(S_{k,m})\) for every \(G \subseteq S_{k,m}\), \(G \ne K_{1,m}\). \(\square\)
Let \(S_{k,(n_1,n_2,\dots,n_k)} \subseteq S_{k,m}\). Define \(A = \{i \mid n_i = 1\}\). For \(k \ge m\), we must restrict subgraphs of \(S_{k,m}\) so that satisfy monotonicity property.
Theorem 2.3 If \[k \ge m\] and \(|A| \le \chi_L(S_{k,m}) - 1\) then \(\chi_L(S_{k,(n_1,n_2,...,n_k)}) \le \chi_L(S_{k,m})\).
Proof. Let \(k \ge m\) and from Theorem 2.1, we have that \(\chi_L(S_{k,m}) = m + a\) for \(H(a-1) < K \le H(a)\), \(a \ge 1\). Let \(G = S_{k,(n_1,n_2,\dots,n_k)}\) be any subgraph obtained from \(S_{k,m}\) with \(1 \le n_i \le m\). If \(2 \le n_i \le m\) for each i, then color vertices of G follow the proof of Theorem 2.1. Clearly, the coloring of G is a locating-coloring. Otherwise, we have \(n_i = 1\) for some i, and so \(|A| \ge 1\). If \(|A| \le \chi_L(S_{k,m}) - 1\), then the center x is given color 1, \(l_i \in A\) for each i is colored by 2,3,..., \(\chi_L(S_{k,m})\), respectively and the colors for the other vertices follow the proof of Theorem 2.1. Observe that the color codes of \(l_i\) for each \(l_i \in A\) has value 1 in the 1th-ordinate, 0 in the i th-ordinate, and 2 otherwise, these color codes are unique. For the remaining of the vertices, the color codes are also unique as proven in Theorem 2.1. As the result, the coloring of G is a locating-coloring. So \(\chi_L(S_{k,(n_1,n_2,\dots,n_k)}) \le \chi_L(S_{k,m})\). \(\square\)