Meysam Korivand^a , Doost Ali Mojdeh^b , Edy Tri Baskoro^c , Ahmad Erfanian^d

Institut Teknologi Bandung, Indonesia, and

Center for Research Collaboration on Graph Theory and Combinatorics, Indonesia.

mekorivand@gmail.com, damojdeh@umz.ac.ir, ebaskoro@itb.ac.id, erfanian@um.ac.ir

An edge-locating coloring of a simple connected graph G is a partition of its edge set into matchings such that the vertices of G are distinguished by the distance to the matchings. The minimum number of the matchings of G that admits an edge-locating coloring is the edge-locating chromatic number of G, and denoted by χ 0 L (G). This paper introduces and studies the concept of edgelocating coloring. Graphs G with χ 0 L (G) ∈ {2, m} are characterized, where m is the size of G. We investigate the relationship between order, diameter and edge-locating chromatic number. We obtain the exact values of χ 0 L (Kn) and χ 0 L (Kⁿ − M), where M is a maximum matching; indeed this result is also extended for any graph. We determine the edge-locating chromatic number of the join graphs of some well-known graphs. In particular, for any graph G, we show a relationship between χ 0 L (G + K1) and ∆(G). We investigate the edge-locating chromatic number of trees and present a characterization bound for any tree in terms of maximum degree, number of leaves, and the support vertices of trees. Finally, we prove that any edge-locating coloring of a graph is an edge distinguishing coloring.

Keywords: edge-locating coloring, matching, join graphs, distinguishing chromatic index

Mathematics Subject Classification : Primary: 05C15

DOI: 10.5614/ejgta.2024.12.1.6

Received: 9 November 2023, Revised: 25 February 2024, Accepted: 16 March 2024.

^aDepartment of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

^bDepartment of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

^cCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences,

^dDepartment of Pure Mathematics, Faculty of Mathematical Sciences and Center of Excellence in Analysis on Algebraic Structures, Ferdowsi University of Mashhad, Mashhad, Iran.

1. Introduction

One of the structural and applied topics in graph theory is distinguishing graph vertices and edges by means of different tools. This approach has a relatively old history in graph theory and has used various tools such as distance and automorphism in graphs. In the following, we describe the history of some known concepts that follow such an approach.

In 1977, Babai proposed a concept that today inspires many methods for distinguishing elements of graphs by automorphism [2]. After Albertson and Collins [1] studied this concept in detail and proposed its application, it was widely considered in the name of asymmetric coloring (or distinguishing labelling). Among the parameters defined along this concept, we can mention distinguishing coloring (or proper distinguishing coloring), distinguishing index, distinguishing arc-coloring and distinguishing threshold [12, 18, 19, 26].

The other index related to automorphism is determining set, in which the goal is to identify the automorphism by a subset of graph vertices. This concept were introduced independently by Boutin [6] and Erwin & Harary [14]. The determining numbers of Kneser graphs and Cartesian product of graphs are provided in [6, 8, 7].

One of the most important and well-known concepts that distinguishes the vertices of a graph with respect to distance is the metric dimension. In 1975-76, Slater [28] and Harary & Melter [16] independently introduced and studied this concept for connected graphs. This introduction was a turning point for a branch of research that occupied many researchers, so that after about 50 years this concept is still the foundation of many research projects and applications, even in other sciences such as chemistry and computer science. Due to its many applications in different sciences and other versions of the metric dimension, it has been introduced. In recent years, this concept has received more attention than in the past. We recommend the reader who needs more information about this concept refer to two recently raised surveys that discuss in detail the different versions of the metric dimension and its applications [22, 29].

The edge metric dimension is one of these concepts derived from the metric dimension, where the goal is to distinguish the edges from a set of graph vertices [20]. Of course, in the metric dimension literature, we know the two concepts as edge metric dimension. The second case, which is also discussed in this article, means the least number of edges that resolve the vertices of a graph with respect to the distance [24].

In 2002, Chartrand et. al. introduced a coloring that we know as locating coloring [11]. In this coloring, the goal is to distinguish the vertices of a graph by their distance from a partition of the vertex set. The locating coloring has been the subject of many researchers; for more details, see [3, 4, 10, 17, 23, 27].

In this paper, our goal is to distinguish the vertices of a connected graph by the distance of the matchings that partition the edge set. The exact definition of edge-locating coloring is given below.

Let G be a simple connected graph. Let c : E(G) −→ N be a proper edge coloring of G, in which adjacent edges of G have different colors. Let π = (C1, C2, . . . , Ck) denote the ordered partition of E(G), that is the color classes admitted of c. For a vertex v of G, the edge color code cπ(v) is the ordered k-tuple (d(v, C1), d(v, C2), . . . , d(v, Ck)), where d(v, Ci) = min{d(v, e)|e ∈ Ci} for 1 ≤ i ≤ k, and d(v, e) = min{d(v, x), d(v, y)|e = xy}.

The coloring c is called an edge-locating coloring of G if distinct vertices of G have different

edge color codes. The edge-locating chromatic number χ 0 L (G) is the minimum number of colors needed for an edge-locating coloring of G. The rest of the notations used without definition in this paper are from reference [5].

In this paper, we generally seek to investigate the behavior of the edge-locating coloring in some family graphs. Specifically, in Section 2, we compute the edge-locating coloring for paths, cycles, and complete bipartite graphs. Also, we characterize all graphs G of size m with the property that χ 0 L (G) = k, where k ∈ {2, m}. Moreover, we present some bounds for the edgelocating chromatic number. In Section 3, we derive the edge-locating coloring of complete graphs and the complete graphs minus some matchings. Moreover, in this section, we derive a sharp upper bound for the edge-locating chromatic number of a graph having a perfect matching and we extend it for a maximum matching. In Section 4, we will determine the edge-locating chromatic number of join graph G+ H, where G and H are some well known graphs. In Section 5, we will examine the edge-locating chromatic number of trees. In particular, we compute the edge-locating chromatic number of the double star graphs and generalize it. Moreover, we present a characterization bound for any tree in terms of maximum degree, number of leaves and number of support vertices of trees.

We saw that there are several automorphism bases and distance bases coloring and index in graph theory. In general, these two concepts travel their research paths without paying attention to each other. However, some relationships between some of these parameters have been proven. It has been shown that any resolving set of a graph is a determining set. Determining sets and resolving sets were jointly studied in [9, 15, 25]. Also, Korivand, Erfanian, and Baskoro recently showed that any locating coloring is a distinguishing coloring [21]. In Section 6, we prove that any edge-locating coloring of a graph is an edge distinguishing coloring. Also, we bound the edge-locating chromatic number to edge metric dimension and chromatic index.

2. General results

The edge-locating chromatic number is defined for graphs with more than two vertices. Since graphs are simple if all edges assign distinct colors then clearly the edge color codes of vertices are different. For any simple connected graph G with size m > 2,

\[2 \le \chi_L'(G) \le m.\]

Another natural bound for edge-locating chromatic number is χ 0 (G) ≤ χ 0 L (G). Since χ 0 (Pn) = 2, χ 0 L (Pn) ≥ 2, for n ≥ 3. Clearly χ 0 L (P3) = 2. Assume that n > 3. If we consider an edge 2 coloring of Pⁿ then any two vertices of Pⁿ that are not pendant vertices have the same edge color code. Thus χ 0 L (Pn) ≥ 3. Now, for an edge-locating 3-coloring of Pn, n ≥ 4, it is enough to assign color 3 to an edge with a pendant end vertex, and other edges of Pⁿ coloring by color 1 and 2, alternately. Therefore, χ 0 L (Pn) = 3. Now, we can present the next proposition.

Proposition 2.1. For positive integer \[n\], \(\chi'_L(P_n) = \begin{cases} 2, & \text{if } n = 3, \\ 3, & \text{if } n \geq 4. \end{cases}\)

The distance between two edges e¹ and e² is defined by min{d(aⁱ , b^j ) | 1 ≤ i, j ≤ 2, e¹ = a1a2, e² = b1b2}.

Theorem 2.1. For any integer \[n \ge 3\], \(\chi'_L(C_n) = \begin{cases} 3, & \text{if } n = 3, \\ 4, & \text{if } n \ge 4. \end{cases}\)

Proof. For n=3, \(\chi'(C_n)=\chi'_L(C_n)=3\). Now, we claim that \(\chi'_L(C_n)>3\), for \(n\geq 4\). For a contradiction, assume that the edges of \(C_n\) are colored by three colors. Without loss of generality, we may suppose that the color 3 is the least used color in \(C_n\). Let \(e=v_1v_2\) denote the only edge colored by 3. Since \(n\geq 4\), for n odd, the vertices \(v_3,v_n\) have the same edge color code. For n even, the vertices \(v_1,v_2\) have the same edge color code. Hence, color 3 is assigned to at least two edges. Assume that e and f are two edges with color 3, such that \(d(e,f)=\min\{d(e_1,e_2)|e_1,e_2\in \mathcal{C}_3\}\). If the distance between e and f are at least two, then \(c_\pi(a)=c_\pi(b)\), where \(a\sim v\sim u\sim b\) and e=vu. Let \(\{e_1,e_2,\ldots,e_m\}\) be a maximal alternative matching such that \(d(e_i,e_{i+1})=1\) and \(e_i\in\mathcal{C}_3\), for \(1\leq i\leq m\). Since the color 3 is the least color used in \(C_n\), the vertices a and b with the property that \(d(a,e_1)=d(b,e_m)=1\) and a,b are not end points of \(e_i,1\leq i\leq m\), have the same edge color code (0,0,1). Therefore, in all cases we have two vertices with the same edge color code, a contradiction.

Finally, we present an edge-locating 4-coloring of \(C_n\) in such a way that assigns to two incident edges colors 3 and 4, and other edges coloring by 1 and 2, alternately.

Proposition 2.2. Let G be a graph. Then \(\chi'_L(G) = 2\) if and only if \(G \cong P_3\).

Proof. Only one implication requires proof. Assume that \(\chi'_L(G) = 2\). Hence \(\Delta(G) = 2\). This implies that G is a cycle or a path. On the other hand, by Proposition 2.1 and Theorem 2.1, we know that all cycles and paths except \(P_3\) need at least three colors for an edge-locating coloring. So the result is immediate.

Theorem 2.2. For distinct integers \[p, q \ge 2\], \(\chi'_L(K_{p,q}) = \max\{p, q\} + 1\) and \(\chi'_L(K_{p,p}) = p + 2\).

Proof. For the comfort of calculation, we consider matrix \(p \times q\), \(A = [a_{b_i c_j}]\), where \(\{b_1, b_2, \ldots, b_p\}\) and \(\{c_1, c_2, \ldots, c_q\}\) are the partite sets of \(K_{p,q}\), and \(a_{b_i c_j}\) is the color of edge \(b_i c_j\). Thus, for any fixed integer i, \((1 \le i \le p)\), row \((a_{b_i c_j})_{j=1}^q\) is the assigned colors of the incidence edges of \(b_i\). Similarly, for any fixed integer j, \((1 \le j \le q)\), column \((a_{b_i c_j})_{i=1}^p\) is the assigned colors of the incidence edges of \(c_j\). An edge-locating coloring of \(K_{p,q}\) gives the following conditions on A.

• (i) All elements in each row (column) are distinct.
• (ii) For i and j, \((1 \le i, j \le p)\), \(\{a_{b_i c_k}\}_{k=1}^q \ne \{a_{b_j c_k}\}_{k=1}^q\).
• (iii) For i and j, \((1 \le i, j \le q)\), \(\{a_{b_k c_i}\}_{k=1}^p \ne \{a_{b_k c_j}\}_{k=1}^p\).

Let p>q. To satisfy conditions (i) and (ii) we need more than p colors. We claim that with p+1 colors matrix A with conditions (i), (ii) and (iii) is constructed. For this, let S be \((p+1)\times (p+1)\) matrix consisting of all column matrices of colors \([1,2,\ldots,p,p+1]^t\), \([p+1,1,\ldots,p-1,p]^t\), \([p+1,1,\ldots,p-1,p]^t\). Now, assume that A is the sub-matrix of S consisting of first p rows and q columns, where \((a_{b_ic_1})_{i=1}^p=[1,2,\ldots,p]^t\), \((a_{b_ic_2})_{i=1}^p=[p+1,1,\ldots,p-1]^t\), \(\ldots\), \((a_{b_ic_q})_{i=1}^p=[p+3-q,p+4-q,\ldots,p+q+1-q,1,2,\ldots,p+1-q]^t\). Then, we can see that all conditions (i), (ii), and (iii) satisfy on A, and the result is available.

For the other implication, let q = p. In this case, to construct matrix A, we need condition (iv) in addition to conditions (i), (ii), and (iii).

(iv) For \[i\] and \(j\), \((1 \le i, j \le p)\), \(\{a_{b_i c_k}\}_{k=1}^p \ne \{a_{b_k c_j}\}_{k=1}^p\).

According to the additional condition (iv), all 2p vertices should have distinct edge color sets that are incident to them. First, show that we cannot edge-locating color of \(K_{p,p}\) with p+1 colors. On the contradiction, assume that we can do it. Let the first column be colored with p colors, and don't use color p+1. Hence, all rows use p+1 as a color for a vertex. This shows that every row does not have one of the colors i for \(1 \le i \le p\). On the other hand, since the first column does not use color p+1, at least one column has p+1 as a color and does not take one of the colors in \(1 \le i \le p\) say j and thus, this column and the row, which has no j as a color, have the same edge color code. That is a contradiction. Therefore, \(\chi'_L(K_{p,p}) \ge p+2\).

In the following, we give a way of edge-locating coloring \(K_{p,p}\), by presentation \(p \times p\) matrix

\[A = \begin{pmatrix} 1 & 2 & 3 & \dots & p-1 & p \\ 2 & 3 & 4 & \dots & p & p+1 \\ 3 & 4 & 5 & \dots & p+1 & p+2 \\ 4 & 5 & 6 & \dots & p+2 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ p-1 & p & p+1 & \dots & p-5 & p-4 \\ p+1 & p+2 & 1 & \dots & p-3 & p-2 \end{pmatrix}.\]

All colors are on module p. Also, \(a_{b_p,c_i}=a_{b_{p-1},c_i}+2\), for \(1 \le i \le p\). One can check that matrix A satisfies conditions (i) - (iv).

In Figure 1, we give an illustration of Theorem 2.2, when p=3 and q=2. In this case, the edge-locating chromatic number is 4, and the matrix A is \(\begin{pmatrix} 1 & 4 \\ 2 & 1 \\ 3 & 2 \end{pmatrix}\).

Figure 1. An edge-locating coloring for \(K_{3,2}\).

For an integer p, the graph \(K_{1,p}\) is called a star graph and is shown by \(S_p\).

Theorem 2.3. Let G be a graph with size \(m \geq 2\). Then \(\chi'_L(G) = m\) if and only if \(G \in \{P_4, C_3, C_4, S_m\}\).

Proof. If \(G \in \{P_4, C_3, C_4, S_m\}\), then we have nothing to prove. For the other, assume first that \(\Delta(G) = 2\). So, Proposition 2.1 and Theorem 2.1 conclude that \(G \in \{P_4, C_3, C_4, S_2\}\). Let \(\Delta(G) = k\), for \(k \geq 3\). For a contradiction, suppose that \(G \ncong S_m\), for any \(m \geq 3\). Let v be a vertex of G with \(deg(v) = k \leq m-1\). Thus, there exists at least a vertex \(u \neq v\) of G such that \(1 < deg(u) \leq k\). Hence, there exists edge e = uw in G, where \(w \neq v\). Since \(k \geq 3\), we have edges e' = vz and e'' = vx such that at least one of z or x is not in \(\{u, w\}\). Now, we assign color 1 to edges e and e', and color the other edges with distinct colors \(2, 3, \ldots, m-1\) such that, without loss of generality, it is assigned color 2 to edge vu and color 3 to edge e'' = vx. We will show that this coloring is an edge-locating coloring of G. For this, we have \(c_\pi(v) = (0, 0, 0, \ldots)\), \(c_\pi(u) = (0, 0, 1, \ldots)\), \(c_\pi(z) = (0, 1, 1, \ldots)\), \(c_\pi(w) = (0, 1, 2, \ldots)\) if w is not adjacent to x, and if w is adjacent to x the color of wx is 4, then \(d(w, C_4) = 0\) and \(d(z, C_4) \leq 1\). Therefore, these five vertices have distinct edge color codes. For a vertex \(y \notin \{v, u, w, z, x\}\), it is incident to at least one new edge with a new color. Hence \(c_\pi(y) \neq c_\pi(t)\) for \(t \neq y\). This is a contradiction, and then \(G = S_m\).

In the following, we present some bounds for edge-locating coloring of a graph.

Theorem 2.4. Let G be a graph with order n and \(diam(G) = d \ge 3\). Then,

\[\log_d n + 2 \le \chi'_L(G).\]

Proof. The edge color code of any vertex of G has \(\chi'_L(G)\) coordinates. Since each vertex is incident to at least one edge, at least one coordinate is 0. Let v be a vertex, and e=vu. There exists an edge e'=uw that \(w\neq v\). The color of e' is different from e, and the coordinate of the edge color code of v according to color e' is 1. So, the two coordinates of any vertex of G are determined, and other coordinates can be filled by k, \(0\leq k\leq d-1\). Since in any edge-locating coloring, each vertex must have a unique edge color code, \(n\leq d^{(\chi'_L(G)-2)}\), and the result is obtained.

Theorem 2.5. Let G be a graph with \(diam(G) = d \ge 3\) and \(\chi'_L(G) = k\). Then,

\[\log_{(d-1)}\left[\frac{n_i}{\binom{k}{i}}\right] + i \le k, \quad for \ 1 \le i \le \Delta.\]

Where, \(n_i\) is the number of vertices of degree i.

Proof. We can color the incident edges of a vertex of G of degree i with \(\binom{k}{i}\) ways. Thus, \(\left[\frac{n_i}{\binom{k}{i}}\right]\) numbers of vertices of degree i have the same colored incident edges. So, the other coordinates of this vertices can be filled by \(\ell\), \(1 \leq \ell \leq d-1\). Therefore, \(\left[\frac{n_i}{\binom{k}{i}}\right] \leq (d-1)^{(\chi'_L(G)-i)}\), for any \(1 \leq i \leq \Delta\), and the result is immediate.

3. Complete graphs and matchings

In this section, we determine the edge-locating coloring of complete graphs and the complete graphs minus some matchings. Then we generalize this subject to arbitrary graphs.

3.1. Complete graphs

A matching M of a graph is a set of independent edges. A vertex is M-saturated if it is incident with an edge of M, and M-unsaturated otherwise. A matching is said to be maximum if for any other matching \(M^*\), \(|M| \geq |M^*|\). A matching M is perfect if it saturates all vertices of G. Let \(K_n - e\) denote the complete graph \(K_n\) minus one edge.

Theorem 3.1. For any even \(n \ge 4\), \(\chi'_L(K_n) = n + 1\).

Proof. First, we show that \(\chi'_L(K_n) \geq n+1\). Let n be an even integer with \(n \geq 4\). Let \(V(K_n) = \{v_1, v_2, \ldots, v_n\}\). Then \(\chi'_L(K_n) \geq n\). However, we will show that \(\chi_L(K_n) \neq n\) for any even \(n \geq 4\). Let c be any proper edge locating coloring of \(K_n\) with n colors. Then, each of at least n/2 colors will appear exactly n/2 times each, and each of at most n/2 colors will appear at most n/2-1 times each. A simple verification shows that, precisely, n/2 different colors (say, colors \(1,2,\ldots,\frac{n}{2}\)) appear n/2 times each, and other colors (namely, colors \(\frac{n}{2}+1,\frac{n}{2}+2,\ldots,n\)) will appear exactly n/2-1 times each. Therefore, every vertex is incident to all colors except color k for some \(k \in \{\frac{n}{2}+1,\frac{n}{2}+2,\cdots,n\}\). This means that there are only \(\frac{n}{2}\) different edge color codes for all n vertices of \(K_n\) with respect to coloring c. Thus, c is not an edge-locating coloring of \(K_n\), and so \(\chi'_L(K_n) \geq n+1\) for any even \(n \geq 4\).

Now we provide an edge-locating coloring of \(K_n\) with n+1 colors. As it is well known, the edge color code of any vertex v is formed by n+1 coordinates, in which two of its coordinates are 1 and the others are 0. Let \(e_{ij}\) be an edge of \(K_n\) with two end vertices \(v_i\), and \(v_j\) where i < j. For defining n+1-edge-locating coloring function \(\alpha\) on \(K_n\), we consider two cases. If \(3 \nmid n+1\), then we define \(\alpha\) on \(K_n\) as follows.

\[\alpha(e_{ij}) = j + i - 2 \ (mod \ n + 1) \ for \ 1 \le i < j \le n.\]

In this case, for any vertex \(v_i\) two coordinates 2i-2 and i-2 of the edge color code of \(v_i\) are 1 and the others are 0. Since 2i-2=j-2 and i-2=2j-2, 3i=0 (mod n+1). If \(i\neq j\), then \(\{2i-2,i-2\}\neq\{2j-2,j-2\}\). If \(3\mid n+1\) and n+1=3k, then we define \(\alpha\) on \(K_n\) as follows. If \(e_{ij}\notin\{e_{(lk-1)},e_{(lk)}:1\leq l\leq k-2\}\)

\[\alpha(e_{ij}) = j + i - 2 \pmod{n+1}\] for \(1 \le i < j \le n\).

For \(e_{ij} \in \{e_{(l(k-1))}, e_{(lk)} : 1 \le l \le k-2\}\), we define

\[\alpha(e_{l(k-1)}) = k + l - 2 \ (l < k-2); \ \alpha(e_{lk}) = k + l - 3 \ (mod \ n+1).\]

In this case, for any vertex \(v_i\), \((i \neq k-1)\), the two coordinates 2i-2 and i-2 of the edge color code of \(v_i\) are 1 and the others are 0. For \(v_{k-1}\) the two coordinates k-2 and k-3 of the edge color code of \(v_{k-1}\) are 1 and the others are 0. Similar to the above method, one can show that, for \(k-1 \notin \{i,j\}, \{2i-2,i-2\} \neq \{2j-2,j-2\}\) and for \(j \neq k-1, \{2j-2,j-2\} \neq \{k-2,k-3\}\). \(\square\)

For instance, consider the edge-locating colorings of \(K_8\) and \(K_{10}\) represented by the two matrices \((8 \times 8)\)-matrices and \((10 \times 10)\)-matrices below, where \(8 + 1 = 9 = 3 \times 3\) and \(3 \nmid 10 + 1\).

The entries ij are the colors of the edge eij with two end-vertices vⁱ and v^j , where i < j. In the matrix, we only wrote the color of eij with i < j. For instance, in K8, the vertex v³ is incident to the colors

{c(e13) = 3, c(e23) = 4, c(e34) = 5, c(e35) = 6, c(e36) = 7, c(e37) = 8, c(e38) = 9} or in K10, the vertex v⁴ is incident to the colors {c(e14) = 3, c(e24) = 4, c(e34) = 5, c(e45) = 7, c(e46) = 8, c(e47) = 9, c(e48) = 10, c(e49) = 11, c(e4 10) = 1}.

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Theorem 3.2. For any odd n ≥ 3, χ 0 L (Kn) = n.

Proof. Let n be an odd integer with n ≥ 3. Let V (Kn) = {v1, v2, · · · , vn}. Since ∆(Kn) = n − 1 then χ 0 L (Kn) ≥ n. We are going to show that χL(Kn) = n for any odd n ≥ 3. We define α on Kⁿ as follows:

\[\alpha(e_{ij}) = j + i - 2 \pmod{n} \text{ for } 1 \le i < j \le n.\]

In this case, for any vertex vⁱ , one coordinate (2i − 2) of the edge color code of vⁱ is 1 and the others are 0. Since for i 6= j, 2i − 2 6= 2j − 2, this coloring is an edge-locating coloring. Thus α is an edge-locating chromatic coloring of Kn, and so χ 0 L (Kn) = n for odd n.

Edge-locating coloring of graphs | M. Korivand et al.

\[K_{11}: \begin{pmatrix} -1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ --- & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ --- & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 1 \\ --- & --- & 7 & 8 & 9 & 10 & 11 & 1 & 2 \\ --- & --- & --- & 9 & 10 & 11 & 1 & 2 & 3 & 4 \\ --- & --- & --- & --- & 2 & 3 & 4 & 5 \\ --- & --- & --- & --- & 4 & 5 & 6 \\ --- & --- & --- & --- & --- & 8 \\ --- & --- & --- & --- & --- & 8 \end{pmatrix}\]

For k ≥ 1, let M^k be a matching with k edges.

In the proof of Theorem below, we can also use the method of the proof of Theorem 3.4 by the proof of Theorem 3.2.

Theorem 3.3. For n ≥ 1 and 1 ≤ k ≤ n, we have that

\[\chi'_L(K_{2n+1}\backslash M_k) = \begin{cases} 2n+1, & \text{if } 1 \le k \le n-1, \\ 2n, & \text{if } k = n. \end{cases}\]

Proof. For 1 ≤ k ≤ n − 1, the graph K2n+1\M^k has at least two vertices of degree 2n. Thus, χ 0 L (K2n+1\Mk) ≥ 2n + 1. But if k = n, since K2n+1 \ Mⁿ has exactly one vertex of degree 2n, then χ 0 L (K2n+1\Mn) ≥ 2n. To obtain an edge-locating (2n)-coloring of K2n+1\Mⁿ from the edge-locating (2n + 1)-coloring of K2n+1 (in Theorem 3.2) we can remove the edges of a monochromatic Mn. Thus, the proof is observed.

If we note the proof of Theorem 3.1, there exists a χ 0 L (K2n) with 2n + 1 colors such that each edge-locating color class has at least n − 1 edges and we can easily to see exactly 2n color classes have n − 1 edges, and one color class has n edges. The edge coloring is such that it can be said that color 2n − 1 was used for n edges, and the rest of the colors were used for n − 1 edges each. Therefore, we have.

Theorem 3.4. Let \[n \geq 2\]. Then \(\chi'_{L}(K_{2n} \backslash M_{k}) = 2n\) if \(k \in \{n-1, n\}\).

Proof. By Theorem 3.1, we have that χ 0 L (K2n) = 2n + 1 for n ≥ 2. As we mentioned in the above, there is exactly one perfect matching Mⁿ with a monochromatic and 2n matchings Mn−¹ with a monochromatic each. Thus, we get an edge-locating 2n-coloring of Kn\M^k for k ∈ {n − 1, n}.

As an immediate result of Theorems 3.1 and 3.4, we have.

Corollary 3.1. Let m be a positive integer and m ≤ n − 1. Then there exist m matchings Mn−¹ in which χ 0 L (K2ⁿ − m(Mn−1) ∪ Mn) = 2n − m.

3.2. Matchings

In other words, an edge-locating coloring of a graph G is a partition of its edge set into matchings such that the vertices of G are distinguished by the distance of the matchings. The minimum number of the matchings of G that admit an edge-locating coloring is the edge-locating chromatic number of G.

Theorem 3.5. Let G be a graph with order n ≥ 5 and size m. If G has a perfect matching, then χ 0 L (G) ≤ m − n/2 + 1. This bound is sharp for cycle C⁶ and path P6.

Proof. Let M be a perfect matching of G. Color all edges of M with color 1, and other edges with distinct colors. We will show that this coloring is an edge-locating coloring of G. Note that vertices of G cannot be distinguished by the color 1. Consider an arbitrary vertex v of G.

Suppose first that N(v) = {u}. So, vu ∈ M. It is enough to investigate the vertices that have distance one from edge(s) e = uw, for w ∈ N(u) \ {v}. Let N(u) \ {v} = {w}. If deg(w) ≥ 3, there exists a vertex x adjacent to w such that xw /∈ M. Hence, any vertex of N(w)\{u} and vertex v are distinguished by the color of xw. If deg(w) = 2, since n ≥ 5, there exists an edge f = zy such that {z} = N(w) \ {u} and y /∈ {v, u, w}. Thus, f /∈ M, and v and z are distinguished by the color of f. Assume that |N(u) \ {v}| ≥ 2. A vertex z has distance one from edges e = uw, for w ∈ N(u) \ {v}, when N(u) \ {v} ⊆ N(z). In this situation, there exists a vertex x ∈ N(u) \ {v} such that xz /∈ M. Therefore, v and z have different distances from xz, and the result is immediate.

Assume that deg(v) = 2. There exists at least an edge e = vu /∈ M, for a vertex u of G. Assign color 2 to e. The only vertex that can be a candidate for the edge color code equal to v is u. Since u can not be a pendant vertex, we have N(u) \ {v} 6= ∅. If |N(u) \ {v}| ≥ 2, there exists a vertex w ∈ N(u) \ {v} such that uw /∈ M. Thus, the color of uw distinguishes v and u. Let |N(u) \ {v}| = 1. Suppose that N(u) \ {v} = {z}. So, uz ∈ M. If deg(z) ≥ 2, then there exists a vertex w such that zw /∈ M. If there is edge vw, then we have a cycle with vertices v, u, z, and w. Hence, we must have at least one vertex in this cycle with a degree greater than 2. Clearly, vertices z or w can have a degree of more than 2. Since vw ∈ M, in all possible cases, vertices v and u have different an edge color codes. Also, if deg(z) = 1, there exist an edge f /∈ M with d(v, f) = d(u, f) − 1, and the result is available.

Finally, let deg(v) ≥ 3. In this case, consider vertices x, y, and z as neighbors of v such that xv ∈ M. This implies that yv, zv /∈ M. Now, the colors of yv and zv distinguish v with the other vertices of G.

Theorem 3.5 can be extended for maximum matching.

Theorem 3.6. Let G be a graph with order n ≥ 5 and size m. If G has a max matching M with |M| = k, then χ 0 L (G) ≤ m − k + 1. This bound is sharp for cycle C5, path P5, star K1,n−¹ for n ≥ 2 and double star Sp,1.

Proof. Let M be a maximum matching of G with |M| = k. It is clear that M saturates 2k vertices, and n − 2k vertices cannot be saturated by M. We add n − 2k vertices to G and make each of them adjacent to a vertex that is not saturated. Then, the resulted graph is of order 2n − 2k, size m + n − 2k and has a perfect matching of size k + n − 2k = n − k. Now, Theorem 3.5 implies that χ 0 L (G) ≤ m + n − 2k − (n − k) + 1 = m − k + 1.

Theorem 3.7. Let G be a graph with order n ≥ 4 and size m. If G has k edge-disjoint perfect matchings M = M¹ ∪ M² ∪ · · · ∪ M^k and G\M is a connected spanning subgraph of G, then χ 0 L (G) ≤ m − kn/2 + k.

Proof. Let M = M¹ ∪M² ∪· · ·∪M^k be k edge-disjoint matchings in G. Let G\M be a connected subgraph. Then, establish an edge coloring α on G by assigning a distinct color to each matching and assigning distinct colors to all remaining edges of G\M. Certainly, this coloring α is an edge proper coloring of G. Since G\M is a connected spanning subgraph, then there are no two vertices incident to the same set of colors. This means that every vertex has a distinct edge color code. Therefore, α is an edge-locating coloring of G.

As a closing remark, we raise the following question: Is an edge-locating chromatic number of a graph monotonic? Precisely, is it true that if G is a proper subgraph of H, then χ 0 L (G) ≤ χ 0 L (H)? We know that the metric dimension of a graph is not monotonic, since if G is a star K1,n−¹ with n ≥ 5 and H is a graph formed from G by adding one edge connecting two end-point vertices, then dim(G) > dim(H). The locating chromatic number of a graph is also not monotonic, since if G = C⁴ and H is a graph formed from C⁴ by adding two pendant edges to two consecutive vertices of C4, then 4 = χL(G) > χL(H) = 3.

Theorem 3.8. The edge-locating chromatic number of a graph is not necessarily monotonic.

Proof. For a positive integer n, let Tⁿ denote the perfect binary tree, i.e., Tⁿ is a tree with a root r of degree 2 and other vertices of degree 3 or 1 in which the distance between the root vertex r and any leaf is n. Let G denote the graph obtained from Tⁿ by making adjacent a pendant edge to r in T3. We will show that χ 0 L (G) ≥ 5. For a contradiction, since G has at least two vertices of degree 3, we assume that χ 0 L (G) = 4. Without loss of generality, we may suppose that the incident edges of r are colored by 1, 2, and 3, such that the leaf is colored by 1. It is clear that G has seven vertices with degree 3. The distance between any vertex of degree 3 and any color class is at most 2. So, we don't have more than two vertices of G with the same colored incident edges. Since 4 3 = 4, there are 4 ways for coloring the incident edges of a vertex of degree 3. Hence, for exactly one vertex of degree 3, the edges incident on it take a set of three colors, and for the rest of the vertices of degree 3, for both vertices, the edges incident on them take a set of three colors. Vertex r is the only vertex with colored incident edges 1, 2, and 3. Any other vertex with these colored incident edges has distance 1 from color 4. We say that the vertices of depth i in G are the vertices of T³ with distance i from r. In T3, there are two children, as r^L and rR, on the left and right of r. The children and grandchildren of r^L and rR, called by left part and right part, receptively. Now, we want to determine the position of two vertices of degree 3 with colored incident edges 2, 3 and 4. Clearly, these two vertices cannot be in depth 1 or the same part simultaneously. If these two vertices are in different parts, then one edge between depth 1 vertex and depth 2 vertex must be colored by 1, and the other one is not colored by 1. This implies that we have three vertices with colored incident edges 2, 3 and 4, which is a contradiction. Assume that there are two vertices of degree 3 with colored incident edges 2, 3, and 4 in depth 1 and depth 2. Similarity, distinguishing these two vertices gives us another vertex with colored incident edges 2, 3, and 4, a contradiction. Therefore, χ 0 L (G) ≥ 5 and obviously, by assigning 5 colors to the edges of G, we can show that

χ 0 L (G) = 5. Let H denote the graph obtained from G with join r to a pendant vertex in depth 3. One can check that χ 0 L (H) = 4 (see Figure 2). Therefore, there exist graphs G and H that G ⊂ H and χ 0 L (H) ≤ χ 0 L (G).

Figure 2. Graph H with edge-locating chromatic number 4.

4. Join graphs

For any graphs G and H, a join graph between G and H, denoted by G+H, is a graph obtained by connecting all vertices of G with all vertices of H. In particular, if G = K¹ and H is a cycle Cn, the graph K¹ + Cⁿ is called a wheel, and it is denoted by Wn. The graph K¹ + Pⁿ is called a fan, graph and it is denoted by Fn. The graph K¹ + nK² is called a windmill graph and it is denoted by Wm(2n). The graph K² + nK² is called a book graph with n pages, and it is denoted by Bn. In this section, we will determine the edge-locating chromatic of join graph G + H.

Theorem 4.1. For any graphs \[G\] and \(H\), \(\chi'_L(G+H) \ge max\{\Delta(G) + |V(H)|, |V(G)| + \Delta(H)\}\).
Proof. It is straightforward since \(\Delta(G+H) = max\{\Delta(G) + |V(H)|, |V(G)| + \Delta(H)\}\).

The upper bound is sharp and achieved by a wheel, a fan, or a windmill, as stated in the following theorem.

Theorem 4.2. The following are the edge-locating chromatic number for special join graphs:

• For n ≥ 4, χ 0 L (Wn) = n.
• For n ≥ 4, χ 0 L (Fn) = n; χ 0 L (F2) = 3, and χ 0 L (F3) = 4.

• For n ≥ 3, χ 0 L (Wm(n)) = 2n, χ 0 L (Wm(2)) = 5
• For n ≥ 3, χ 0 L (Bn) = 2n + 2, and χ 0 L (B2) = 6.

Proof. For wheels and fans, let V (Wn) = V (Fn) = {c, v1, v2, . . . , vn} with a center c and n ≥ 4. Since ∆(Wn) = ∆(Fn) = n then χ 0 L (Wn) ≥ n and χ 0 L (Fn) ≥ n. Now, construct an edge n-coloring α of Wⁿ (as well as of Fn) as follows.

\[\alpha(e) = \begin{cases} i, & \text{if } e = cv_i, \\ i + 2 \bmod n, & \text{if } e = v_i v_{i+1}. \end{cases}\]

Note that all indices are in mod n. In wheels, the color code of vertex vⁱ under α will have zero entries in the i th , (i + 1)th, and (i + 2)th (in modulo n) positions. In fans, the color code of v¹ has zeros in the 1 st and 3 rd positions; the color code of vⁿ has zeros in the 1 st and the n th positions. The color codes for other vertices are the same as for wheels. The color code of vertex c has all zero entries. Therefore all color codes are different for wheels as well as on fans. For small cases, it is easy to verify that χ 0 L (F2) = 3, and χ 0 L (F3) = 4.

In windmills Wm(n), for n ≥ 3, let V (Wm(n)) = {c, v1, v2, . . . , v2n} with a center c and E(Wm(n)) = {vivi+1| for all odd i ≤ 2n} ∪ {cvⁱ | for all i ≤ 2n}. Since ∆(Wm(n)) = 2n, then χ 0 L (Wm(n)) ≥ 2n. Now, construct an edge (2n)-coloring α of Wm(n) as follows.

\[\alpha(e) = \begin{cases} i, & \text{if } e = cv_i, \\ i + 2 \bmod n, & \text{if } e = v_i v_{i+1} \text{ and } i \text{ is odd.} \end{cases}\]

Note that all indices are in mod n. This coloring α is easily verified as an edge-locating coloring.

In books Bn, for n ≥ 3, let V (Bn) = {c1, c2, v1, v2, · · · , v2n−1, v2n} and E(Bn) = {c1c2} ∪ {c1v2i−1, c1v2ⁱ , c2v2i−1, c2v2ⁱ | 1 ≤ i ≤ n} ∪{v2i−1v2ⁱ | 1 ≤ i ≤ n}. Since ∆(Bn) = 2n + 1 and there are two vertices of degree 2n + 1, then χ 0 L (Bn) ≥ 2n + 2. Now, construct an edge (2n + 2) locating coloring α of Bⁿ as follows.

\[\alpha(e) = \begin{cases} 1, & \text{if } e \in \{c_1c_2, v_{2i-1}v_{2i} | 1 \le i \le n\}, \\ i+1 \pmod{2n}, & \text{if } e \in \{c_1v_{2i-1}, c_2v_{2i} | 1 \le i \le n\}, \\ n+2, & \text{if } e = c_1v_2, \\ n+2+i \pmod{2n}, & \text{if } e \in \{c_1v_{2i+2}, c_2v_{2i-1} | 1 \le i \le n-1\}, \\ 2n+2, & \text{if } e = c_2v_{2n-1}. \end{cases}\]

It is easy to verify that this coloring α is an edge-locating coloring.

Theorem 4.3. Let G be a connected graph and H = G + K1. Then we have

• (i) If G is graph of order 2n and ∆(G) ≤ 2n − 2, then χ 0 L (H) ≤ 2n. Furthermore, χ 0 L (H) = 2n + 1 if and only if G has at least one vertex of degree 2n − 1,
• (ii) If G is a graph of order 2n + 1 and ∆(G) ≤ 2n − 1, then χ 0 L (H) ≤ 2n + 2, and equality holds if G has at least one vertex of degree 2n

Proof. (i). Let |V (G)| = 2n. If ∆(G) ≤ 2n − 2, then G ⊆ K2ⁿ \ Mn. From Theorem 3.4 χ 0 L (K2ⁿ \ Mn) = 2n and then χ 0 L (G) ≤ 2n. Now we have, H ⊆ K2n+1 \ Mⁿ and from Theorem

3.3 χ 0 L (K2n+1 \ Mn) = 2n and then χ 0 L (H) ≤ 2n.

Now suppose that G has at least one vertex of degree 2n − 1. Then H has at least two vertices of degree 2n, and hence χ 0 L (H) ≥ 2n + 1. On the other hand, H ⊆ K2n+1 \ M^k for k ≤ n − 1. By Theorem 3.3, χ 0 L (K2n+1 \Mk) = 2n+ 1, and thus χ 0 L (H) ≤ 2n+ 1. Therefore, the equality holds. Conversely, suppose that the equality holds and, in contradiction, G has no vertex of degree 2n−1, which means that ∆(G) ≤ 2n − 2. From the first part of the proof, since the order of G is 2n, hence χ 0 L (H) ≤ 2n, that is a contradiction.

(ii). Let |V (G)| = 2n + 1. If ∆(G) ≤ 2n − 1, then G ⊆ K2n+1 \ Mⁿ ∪ M^k where k ≥ 1. From Theorem 3.3, χ 0 L (K2n+1 \ Mⁿ ∪ Mk) ≤ 2n, and then χ 0 L (G) ≤ 2n. In this case, H + K¹ is a connected graph of order 2n + 2, with exactly one vertex of maximum degree ∆(H) = 2n + 1. Thus we have H ⊆ K2n+2 \ Mⁿ ∪ M^k and from Theorem 3.4 χ 0 L (K2n+2 \ Mⁿ ∪ Mk) ≤ 2n + 2 and then χ 0 L (H) ≤ 2n + 2.

Now suppose that G has at least one vertex of degree 2n. Then H has at least two vertices of degree 2n + 1 and hence χ 0 L (H) ≥ 2n + 2. On the other hand, H ⊆ K2n+2 \ Mn. By Theorem 3.4 χ 0 L (K2n+2 \ Mn) ≤ 2n + 2, and thus χ 0 L (H) ≤ 2n + 2. Therefore, the equality holds.

5. Trees

Theorem 5.1. For any double star Sp,q, χ 0 L (Sp,q) = ( p + 1, if p > q p + 2, if p = q. .

Proof. Let G = Sp,q, where p > q, with support vertices v, u of degrees p+1, q+1 and end vertices v1, . . . , vp, u1, . . . , u^q respectively. Then, by Konig's Theorem [13, Theorem 10.8], ¨ χ 0 (G) = p + 1 and hence χ 0 L (Sp,q) ≥ p + 1. On the other hand, if we assign color i to vvⁱ and uuⁱ , and assign color p + 1 to the vertex vu, then cπ(vi) = (1, 1, . . . , d(vⁱ , Ci) = 0, 1, . . . , 1) for 1 ≤ i ≤ p, cπ(v) = (0, 0, . . . , 0), cπ(u) = (0, 0, . . . , 0, d(u, Cq+1) = 1, . . . , d(u, Cp) = 1, d(u, Cp+1) = 0), and cπ(u^j ) = (1, 1, . . . , d(u^j , C^j ) = 0, 1, . . . , d(u^j , Cq) = 1, d(u^j , Cq+1) = 2, . . . , d(u^j , Cp) = 2, d(u^j , Cp+1) = 1) for 1 ≤ j ≤ q. Therefore χ 0 L (Sp,q) = p + 1.

Let p = q. Then χ 0 (Sp,q) = p + 1, and edges color i for vvⁱ and uuⁱ 1 ≤ i ≤ p and color p + 1 for vu. In this case, cπ(v) = (0, 0, . . . , 0) = cπ(u). Now by changing the color edge uu¹ from 1 to p + 2. Then using above method, it can be seen that all vertices have distinct edge color codes. Therefore, χ 0 L (Sp,q) = p + 2.

In general we have,

Theorem 5.2. Let n ≥ 4. There exists a tree T of size m having edge-locating-chromatic number k if and only if k ∈ {3, 4, . . . , m − 1, m}.

Proof. For k = 3, consider T = Pm+1 by Theorem 2.1. For k ≥ 4, let T be a tree with vertex set {v1, v2, . . . , vm+1} where vertex v² is of degree k, vertices v1, v3, v4, . . . , vk, vm+1 of degree 1, and other vertices are of degree 2. Now if we assign i to edge v2vⁱ , (1 ≤ i 6= 2 ≤ k + 1), assign 2 and 1 to other edges alternately, then for this T, it is obvious to see that χ 0 L (T) = k.

Theorem 5.3. Let T be a tree with k support vertices v1, v2, · · · , vk, and `<sup>i</sup> leaves adjacent to v<sup>i</sup> , where `¹ ≤ `<sup>2</sup> ≤ · · · ≤ `k. Let ei,j be the pendant edges corresponding to the support vertex vⁱ where 1 ≤ j ≤ `<sup>i</sup> and T <sup>0</sup> be the induced subgraph of non-leaves of T. If ∆(T) < m = P<sup>k i</sup>=1 `ⁱ . Then χ 0 L (T) ≤ ∆(T 0 ) + `^k + k − 1. Equality holds if and only if T = Sp,p.

Proof. We can consider an edge proper ∆(T 0 )-coloring of T 0 , with colors 1, 2, . . . , ∆(T 0 ). Also, color the `<sup>k</sup> pendant edges with distinct colors ∆(T 0 ) + 1, ∆(T 0 ) + 2, . . . , ∆(T 0 ) + `k. Now assign colors ∆(T 0 )+ 1, ∆(T 0 )+ 2, . . . , ∆(T 0 )+`<sup>i</sup> −1, ∆(T 0 )+`^k +i to the edges ei,1, · · · , ei,`<sup>i</sup> if `ⁱ ≥ 2 or assign color ∆(T 0 ) + `<sup>k</sup> + i to edge ei,`ⁱ if `ⁱ = 1. Now, let v and u be two arbitrary vertices of T. Let Pv−^u denote the path between v and u, and P be a maximal path that contains Pv−u. There exist two leaves e and e ⁰ on P such that the colors of e and e 0 are distinct and distinguish vertices v and u.

For equality, if T = Sp,p (p ≥ 2) Theorem 5.1 deduces the result. Conversely, let χ 0 L (T) = ∆(T 0 ) + `<sup>k</sup> + k − 1 and T 6= Sp,p. If T = Sp,q, where p ≥ q + 1, then Theorem 5.1 shows that χ 0 L (T) = p + 1 6= 1 + p + 1 = p + 2, a contradiction. Hence T has at least k ≥ 3 support vertices, ∆(T 0 ) ≥ 2 and T <sup>0</sup> has at least two leaves, say vr, v<sup>t</sup> , and one non leaf, say v<sup>i</sup> . Suppose v<sup>k</sup> is not a leaf in T 0 , since `^r ≤ `k, then the pendant edges er,j s corresponding to v<sup>r</sup> can be colored with the colors of the pendant edges ek,j s corresponding to vk. Suppose v<sup>k</sup> is a leaf in T 0 , then the pendant edges ei,j s corresponding to v<sup>i</sup> can be colored with the colors of the pendant edges ek,j s corresponding to vk. In the two above cases, other pendant edges corresponding to other support vertices can be colored by the method in the first part of the theorem. Therefore χ 0 L (T) ≤ ∆(T 0 ) + `^k + k − 2. This contradiction presents T = Sp,p.

Theorem 5.4. Let T be a tree with m ≥ 3 leaves. If ∆(T) = m then χ 0 L (T) = m. If ∆(T) < m then χ 0 L (T) ≤ ∆(T 0 ) + m, where T 0 is the induced subgraph of non-pendant vertices of T.

Proof. Assume first that ∆(T) = m. Let N(v) = {w1, w2, . . . , wm}, for a vertex v of T. Let v1u1, v2u2, . . . , vmu^m be the leaves of T such that vi's are pendant vertices, for 1 ≤ i ≤ m. For any i, 1 ≤ i ≤ m, suppose that Pⁱ is the v − vⁱ path that contains vertex wⁱ , 1 ≤ i ≤ m. Since ∆(T) = m, V (Pi) ∩ V (P^j ) = {v}, for any i and j, 1 ≤ i, j ≤ m. Consider a coloring of T in such a way that for any i, 1 ≤ i ≤ m − 1, the edges of Pⁱ (Pm) are colored by colors i (m) and i + 1 (1), alternately, such that edges vwⁱ are colored by i, for 1 ≤ i ≤ m. Any non-pendant vertex of Pⁱ (Pm) has a distance zero from Cⁱ (Cm) and Ci+1 (C1), and distance more than zero from other colors. Hence, each non-pendant vertex of T is distinguished by other vertices. On the other hand, vⁱ (vm) has a distance zero from one of the color classes Cⁱ (Cm) and Ci+1 (C1), and distance one from another class, for any i, 1 ≤ i ≤ m, that |V (Pi)| ≥ 3. There exist only some elements of N(v) \ V (Pi) (N(v) \ V (Pm)) that can have the same coordinates according to the color classes Cⁱ (Cm) and Ci+1 (C1). Let z ∈ N(v) ∩ V (Pi). If |V (Pi)| ≥ 3, then degree z is 2 and the result is obtained. If z is a pendant vertex, then since m ≥ 3, there exists a color class C^j such that the distance of z from C^j is one and the distance of vⁱ from C^j is more than one. Therefore, all vertices of T have a different edge color code, and the result is available.

For the other implication, by [13, Theorem 10.8], we can consider an edge proper ∆(T 0 ) coloring of T 0 , with colors 1, 2, . . . , ∆(T 0 ). Also, color the leaves by distinct colors ∆(T 0 ) + 1, ∆(T 0 ) + 2, . . . , ∆(T 0 ) + m. Now, let v and u be two arbitrary vertices of T. Let Pv−^u denote the

path between v and u and P be a maximal path that contains Pv−u. There exists two leaves, e and e ⁰ on P. The colors of e and e ⁰ distinguish vertices v and u, and the proof is completed.

6. Edge metric dimension and distinguishing chromatic index

The minimum size of subset S of edges of graph G that for any two edges e and e 0 , there exists f ∈ S such that d(e, f) 6= d(e 0 , f), is the edge metric dimension of G and denoted by dimE(G). We say that the set S is an edge basis of G. Actually, the edge metric dimension of a graph G is the standard metric dimension of the line graph L(G). This concept is introduced and studied by Nasir et. al. [24]. Also, Kalinowski and Pilsniak introduced the distinguishing chromatic index in ´ [18], wherein the edge distinguishing coloring is an edge proper coloring such that the only color preserving automorphism is the trivial automorphism. The distinguishing chromatic index χ 0 ^D(G) of a graph G is the minimum number of colors that admit an edge distinguishing coloring. In this section, we study some relations between edge-locating coloring and those concepts.

For any subset S of edges of G, let G − S denote the subgraph of G with vertex set V (G) and edge set E(G) \ S. Let S be an edge basis of G. Consider graph H := G − S and assign colors 1, 2, . . . , χ⁰ (H) to edges H according to a proper edge coloring of H. Also give distinct colors χ 0 (H) + 1, χ⁰ (H) + 2, . . . , χ⁰ (H) + |S| to elements of S. Clearly this coloring is an edge-locating coloring of G. Since χ 0 (H) ≤ χ 0 (G), we have the following bound.

\[\chi'(G) \le \chi_L'(G) \le \chi'(G) + \dim_E(G). \tag{1}\]

Clearly, this bound is sharp. For instance, let G = C2n.

Let vu and wx be two edges in graph G and f ∈ Aut(G). We say that f(vu) = wx, if f(v) = w, and f(u) = x.

Theorem 6.1. Any edge-locating coloring of a graph is an edge distinguishing coloring.

Proof. Let G be a graph with size m and π = (C1, C2, . . . , Cn) be the color classes admitted by an edge-locating coloring c of G. The result is immediate if n = m. Assume that n < m. For a contradiction, suppose that c is not an edge distinguishing coloring of G. Thus, there exists an automorphism f of G that preserves the coloring, and f(ea) = e^b for two edges e^a and e^b in C1. Let e^a = aa⁰ , e^b = bb⁰ , f(a) = b and f(a 0 ) = b 0 . Consider arbitrary color i (1 ≤ i ≤ n) and let d(a, Ci) = d(a, e^a i ) and d(b, Ci) = d(b, e^b i ), for edges e a i and e b ⁱ with color i. We will have

\[d(a, e_i^a) = d(f(a), f(e_i^a)) = d(b, f(e_i^a))\] (2)

and

\[d(b, e_i^b) = d(f^{-1}(b), f^{-1}(e_i^b)) = d(a, f^{-1}(e_i^b)).\] (3)

Since d(a, Ci) ≤ d(a, f ⁻¹ (e b i )) and d(b, Ci) ≤ d(b, f(e a i )), (2) and (3) imply that d(a, Ci) = d(b, Ci). This means that cπ(a) = cπ(b), a contradiction.

Corollary 6.1. For any graph G,

• (i) χ 0 ^D(G) ≤ χ 0 L (G).
• (ii) χ 0 ^D(G) ≤ χ 0 (G) + dimE(G).

By Theorem 16 [18], the equality of Corollary 6.1 (ii) is achieved if and only if G is a path graph, C⁴ or C6. Also, Theorem 16 [18] concludes that χ 0 ^D(G) = χ 0 L (G) = k for k ∈ {∆(G), ∆(G) + 1}.

7. Future Research

Several issues regarding this new concept are still unresolved. Here, we will discuss only a few that arise from our findings. As demonstrated in the previous sections, the edge-locating chromatic number is associated with various well-known graph concepts. One of them is the edge chromatic index. Recall that χ 0 (G) ≤ χ 0 L (G), for a connected graph G. Classifying connected graphs G such that χ 0 (G) = χ 0 L (G) can be valuable. Also, one can check if the edge chromatic index is independent of the edge-locating chromatic number. For this purpose, looking for a graph where the edge chromatic index is m and the edge-locating chromatic number is n, for any integers m and n that m ≤ n. It appears that such a graph is available. For k ≥ 2, let T^k be the perfect binary tree with root a, such that deg(a) = 2, other non-pendant vertices have degree 3, and all pendant vertices have distance k from a. By Konig's Theorem [13, Theorem 10.8], the chromatic index of ¨ T^k is 3, for any k ≥ 2. But as k increases, the edge-locating chromatic number of T^k also increases. If we find the edge-locating chromatic number of T^k and let G be the graph obtained by joining the rote of T^k to a star graph, the question is answered. We end the paper with the following problems.

Problem 1. Prove or disprove that for any connected graph G of order n, χ 0 L (G) ≤ χ 0 L (Kn).

Problem 2. Characterize the class Ψ of connected graphs such that G ∈ Ψ if and only if χ 0 ^D(G) = χ 0 L (G) = k for k ∈ {∆(G), ∆(G) + 1}.

Problem 3. For a connected graph G, is there a significant relationship between χL(G) and χ 0 L (G)?

Acknowledgment

The research has been supported by the 2023 PPMI research grant, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia.

References

• [1] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3(1) (1996), #R18.
• [2] L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Hungar. 29(1–2) (1977), 193–200.

• [3] E.T. Baskoro and Asmiati, Characterizing all trees with locating-chromatic number 3, Electron. J. Graph Theory Appl. 1(2) (2013), 109–117.
• [4] A. Behtoei and B. Omoomi, On the locating chromatic number of the cartesian product of graphs, Ars Combin. 126 (2016), 221–235.
• [5] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer-Verlag, (2008).
• [6] D.L. Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin., 13(1) (2006), Research Paper 78 (electronic), 14 pp.
• [7] D.L. Boutin, The determining number of a Cartesian product, J. Graph Theory 61(2) (2009), 77–87.
• [8] J. Caceres, D. Garijo, A. Gonz ´ alez, A. M ´ arquez, and M. L. Puertas, The determining ´ number of Kneser graphs, Discrete Math. Theor. Comput. Sci. 15(1) (2013), 1–14.
• [9] Caceres, D. Garijo, M.L. Puertas, and C. Seara, On the determining number and the metric ´ dimension of graphs, Electron. J. Combin. 17(1) (2010), Research Paper 63, 20 pp.
• [10] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang, Graphs of order n with locating-chromatic number n − 1, Discrete Math. 269 (2003), 65–79.
• [11] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang. The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002), 89-101.
• [12] K.L. Collins and A.N. Trenk, The Distinguishing Chromatic Number, Electron. J. Combin. 13 (2006).
• [13] G. Chartrand and P. Zhang, Chromatic Graph Theory, Chapman and Hall=CRC Press, Boca Raton, FL, (2009).
• [14] D. Erwin and F. Harary, Destroying automorphisms by fixing nodes, Discrete Math. 306(24) (2006), 3244–3252.
• [15] D. Garijo, A. Gonzalez, and A. M ´ arquez, The difference between the metric dimension ´ and the determining number of a graph, Appl. Math. Comput 249 (2014), 487–501.
• [16] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
• [17] A. Irawan, Asmiati, L. Zakaria, and K. Muludi. The locating-chromatic number of origami graphs, Algorithms 14 167, (2021).
• [18] R. Kalinowski and M. Pilsniak, Distinguishing graphs by edge colourings, ´ European J. Combin. 45 (2015), 124-131.

• [19] R. Kalinowski, M. Pilsniak, and M. Prorok. Distinguishing arc-colourings of symmetric ´ digraphs, Art Discrete Appl. Math. 2 (2023), #P2.04.
• [20] A. Kelenc, N. Tratnik, and I.G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Appl. Math. 251 (2018), 204–220.
• [21] M. Korivand, A. Erfanian, and E.T. Baskoro, On the comparison of the distinguishing coloring and the locating coloring of graphs. Mediterr. J. Math. 20(252) (2023).
• [22] D. Kuziak and I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 [math.CO] (2021).
• [23] D.A. Mojdeh, On the conjectures of neighbor locating coloring of graphs, Theoret. Comput. Sci. 922 (2022), 300-307.
• [24] R. Nasir, S. Zafar, and Z. Zahid, Edge metric dimension of graphs, Ars Combin. 147 (2019), 143-156.
• [25] J. Pan and X. Guo, The full automorphism groups determining sets and resolving sets of coprime graphs, Graphs Combin. 35(2) (2019), 485–501.
• [26] M.H. Shekarriz, B. Ahmadi, S.A. Talebpour, and M. H. Shirdareh Haghighi, Distinguishing threshold of graphs, J. Graph Theory 103 (2022), 359-377.
• [27] I.W. Sudarsana, F. Susanto, and S. Musdalifah, The locating chromatic number for mshadow of a connected graph, Electron. J. Graph Theory Appl. 10(2) (2022), 589–601.
• [28] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
• [29] R.C. Tillquist, R.M. Frongillo, and M.E. Lladser. Getting the lay of the land in discrete space: A survey of metric dimension and its applications. arXiv:2104.07201 [math.CO] (2021).