An L(h; k)-edge labeling of a graph G is the assignment of labels f0; 1; ; ng to the edges in such a way that two adjacent edges get labels with a difference at least h and the labels of distance two edges, i.e., two non-adjacent edges having a common edge connecting them get labels with a difference at least k, where h and k are two given non-negative integers. The span 0h;k(G) is the minimum n such that G admits an L(h; k)-edge labeling. For three given integers n; h and k, an n-circular-L(h; k)-edge labeling f 0 of a graph G is an assignment from integers f0; 1; ; n 1g in such a way that if two edges e and e0 are adjacent then jf 0(e) f 0(e0)jn h and if they are distance two edges then jf 0(e) f 0(e0)jn k, where jxjn = minfx; n xg. The circular span h0;k(G) is the minimum n such that G admits an n-circular L(h; k)-edge labeling. Here, we focus on finding 02;1(G) and 20;1(G) where G is infinite regular triangular grid T6. We work on the conjecture 02;1(T6) = 16 and the bound 20;1(T6) 18 given by Lin and Wu [J. Comb. Opt., 2013]. We prove the conjecture and give a labeling function for T6 such that 20;1(T6) 18 as no labeling function was given by Lin and Wu in this case.
In wireless communication, Channel Assignment Problem (CAP) is known as one of the
fundamental and well-studied problems where the goal is to assign frequency channels
to transmitters such that interference cannot occur. The target of this problem is to
minimize the span of frequency spectrum, where the span is the difference between the
lowest and highest frequencies used in the assignment. The formulation of CAP has
been done in 1980 by Hale [
The span h;k(G) of L(h; k)-vertex labeling is the minimum n such that G admits an
L(h; k)-vertex labeling. After some good years, Griggs and Yeh [
graph G(V; E) is a function f 0 : E ! f0; 1; ; ng; 8e 2 E such that jf 0(e1) f 0(e2)j h when d(e1; e2) = 1 and jf 0(e1) f 0(e2)j k when d(e1; e2) = 2. Here, for any two edges e1 and e2, the distance d(e1; e2) is k0 if at least (k0 1) edges are required to connect e1 and e2.
Like L(h; k)-vertex labeling, the span 0h;k(G) of L(h; k)-edge labeling is the
minimum n such that G admits an L(h; k)-edge labeling. In 2011, Calamoneri did a
rigorous survey [
In the year 1998 Van den Heuvel [
labeling f of a graph G is an assignment from integers f0; 1; ; n 1g in a way that
if two vertices u and v are adjacent, then jf (u) f (v)jn h and if they are distance two
apart then jf (u) f (v)jn k, where jxjn = minfx; n xg. Moreover, the minimum n
such that G admits an n-circular-L(h; k)-labeling is called the circular span h;k(G).
Authors in [
that h k, we can write, h;k(G) + 1 h;k(G) h;k(G) + h.
Naturally this problem as well as the Lemma have their corresponding an edge versions. As in this paper our main work in on edge labeling, we discuss those formally.
edge labeling f 0 of graph G is an assignment from integers f0; 1; ; n 1g in a way that if two edges e and e0 are adjacent, then jf 0(e) f 0(e0)jn h and if they are distance two apart, then jf 0(e) f 0(e0)jn k, where jxjn = minfx; n xg. Moreover, the minimum n such that G admits an n-circular-L(h; k)-edge labeling is called the circular span h0;k(G). The edge version of the Lemma 1 is
that h k, we can write, 0h;k(G) + 1 h0;k(G) 0h;k(G) + h.
Lin and Wu [
They also gave the bound 20;1(T6)
18. 1.1
Our Contributions
In this paper we first focus on the Conjecture 1. We show that 02;1(T6) = 16. We also
give a labeling function for T6 such that 20;1(T6) 18 as no labeling function was
given by Lin and Wu [
u2 u3 u4 y17 y18 y19 y20 y21 y22 For a vertex v, let N (v) denotes the set of neighbors of v and for a set of vertices S, let N (S) = [ N (v). Consider the subgraph G(V; E) of T6 centering the triangle formed v2S by S = fv5; v6; v9g as shown in Figure 2, where V = S [ N (S) [ N (N (S)) and E is the set of all edges which are incident to u where u 2 S [ N (S). Now, we define the set of edges in G into five subsets of edges as following: S1 = fg; b; lg S2 = fd; e; n; o; i; jg S3 = fk; f; a; h; m; cg S4 = fx1; x2; x3; ; x9g S5 = fy1; y2; y3; ; y24g
Our proof approach is as follows. In first few observations and lemma (Observation 1, Observations 2, Observations 3, Observation 4 and Lemma 3) we first investigate if a color c0 is used in S1 or in S2 or in S3, then how many times at maximum it can be reused in G and repetition pattern of the colors such that edges of G can be colored with 15(0; 1; ; 14) colors. In Observation 5, we determine the maximum number of times a color c0 can be used in G if it is not used in S1 [ S2 [ S3. In subsequent observation and lemmas(Observation 6, Lemma 4, Lemma 5) we discuss the scenario when a color c0 2= f5; 10g is unused in S1 [ S2 [ S3 and two consecutive colors c0 and c0 + 1 are used in different types of edges. Based on the discussion and results of the mentioned observations and lemmas, we determine the lower bound of 02;1(T6) when a color cu 2= f5; 10g is unused in S1 [ S2 [ S3 in Theorem 1, Theorem 2 and Theorem 3. In Theorem 4, we determine the lower bound of 02;1(T6) when a color cu 2 f5; 10g is unused in S1 [ S2 [ S3. In Theorem 5, we determine the lower bound of 02;1(T6) when all colors in f0; 1; ; 14g are used in S1 [ S2 [ S3. In all the cases, derived lower bounds of 02;1(T6) are identical.
once more in G.
Proof. Without loss of generality, assume that c0 is used in the edge g. Now, it is clear that c0 can only be used in some edges incident to v11 and v12. Since, edges incident to v11 and v12 are not mutually three distance apart, c0 can only be used at most in one edge.
two more times in G.
Proof. As all the edges in S2 are in symmetric position, without loss of generality we can assume that c0 is used in the edge d. One can verify that some edges incident to v4; v8; v11; v12 only are distant three from d. Note that v4 and v8 are adjacent to each other. Similarly v11 and v12 are also mutually adjacent. Hence c0 can be used two times, once in an edge incident to v4; v8 and the other in an edge incident to v11; v12. But if c0 is used in x5, then c0 cannot be used once more.
three more edges in G.
Proof. Observe that here also all the edges are symmetric, so, without loss of generality we can assume that c0 is used at the edge k. Some edges adjacent to the vertices v1; v4; v8; v11; v12 only are three distance apart from k. It is clear that c0 can be used at the edges adjacent to alternate vertices in the sequence v1; v4; v8; v11; v12. Moreover, it can be observed that each edge in S4 where c0 can be used is adjacent to two vertices in v1; v4; v8; v11; v12. So, if we want to use c0 three more times in G, then c0 must be used at edges adjacent to v1; v8; v12, and the color must be used at edges in S5 only. From Observations 1, 2 and 3 it is clear that colors used to color the edges in S1, S2 and S3 can be used at most two, three and four times in G, respectively. Note that G has 48 edges in total. We need all distinct colors to color the edges in S1 [ S2 [ S3 as they are mutually at most two distance apart. So, we need 3, 6 and 6 distinct colors to color the edges in S1, S2 and S3, respectively. If we can repeat all these color with their maximum potential, then it is possible to color the graph G using 15 colors. Here we state Observation 4 and give the unique repetition pattern of the colors, to color G using 15 colors in Lemma 3. Let H be the subgraph of G induced by the edges in S1 [ S2 [ S3. We say two edges e1 = (u1; v1) and e2 = (u2; v2) as a pair of opposite edges iff d(e1; e2) = 3, d(u1; u2) = 2, d(u1; v2) = 2, d(v1; u2) = 2 and d(v1; v2) = 2.
Proof. Without loss of generality let us consider the pair of opposite edges n and x2 (Figure 2). Let f 0(n) = c0 and f 0(x2) 6= c0. Consider the two triangles fv3; v6; v7g and fv6; v9; v10g. Clearly, c0 cannot be used in any edge incident to v3, v6 and v9. Therefore c0 can be assigned to either an edge incident to v7 or an edge incident to v10 but not both. So, c0 cannot be used either in the subgraph H0 isomorphic to H with S10 = fv3; v6; v7g or in the subgraph H00 isomorphic to H with S100 = fv6; v9; v10g. Hence the proof.
etition of the colors used in subgraph H: (a) each color used at the edges in S3 must be repeated three times more in the edges of S5, (b) each color used at the edges in S2 must be repeated two times more, once in its opposite edge in S4 and the other in an edge in S5, (c) each color used at the edges in S1 must be repeated once more in its opposite edge in S4.
Proof. Observe that the first condition for G to be colored with 15 colors is the colors used in S1, S2 and S3 have to be used two times, three times and four times in G respectively. From the proof of Observation 3 it directly follows that if we want to reuse three times a color c3 that has been used in an edge of S3, then c3 has to be reused at the edges of S5 only. Now assume that c2 be a color used in an edge of S2 then c2 cannot be reused at two edges in S4 as there does not exists two mutually three distant edges in S4 such that c2 can be used. From Observation 4 it follows that c2 should be reused at the corresponding opposite edge in S4 and another edge in S5. Observe that only three edges in S4 remain uncolored now. Again from Observation 4 we can say that if c1 be a color used in an edge of S1, then c1 has to be reused at the corresponding opposite edge in S4 only.
We aim to prove 02;1(T6) = 16. We already know that 02;1(H) = 14 and 02;1(T6)
15 [
edges in G.
Proof. Clearly, c0 is used at edges in S = S4 [ S5. All edges in S are incident to one or two vertices in Q = fv1; v2; v3; v7; v10; v12; v11; v8; v4g. So, c0 can be used at edges adjacent to alternative vertices in the sequence Q. There are nine vertices in Q. If we pick every alternate vertices in the sequence starting from v1, then we end up with a set Q1 of five vertices fv1; v3; v10; v11; v4g. Since, v1 and v4 are adjacent in G, we can give the color c0 to edges incident to either v1 or v4. So, we have only four vertices whose adjacent edges can be colored with c0, and note that that no two edge adjacent to same vertices can be colored with same color. Hence there are at most four edges which can be colored with the unused color. Similarly, if we pick alternate vertices in the sequence starting from v2, then we end up with picking a set Q2 of four vertices fv2; v7; v12; v8g. Again, we similarly argue that at most in four edges we can use the unused color in G.
From Figure 2 it is clear that the subgraph H consists of five vertical edges, five horizontal edges and five slanting edges. Let us denote these three types of edges as Tv; Th and Ts, respectively. Now, we prove some properties of colors used in these three types of edges.
Observation 6 Let f 0(p) = c0 and f 0(q) = c0 + 1 where p; q 2 E(H) and they are different types of edges. Then there exists a H0 isomorphic to H in T6 where either c0 or c0 + 1 cannot be used. Proof. Let us consider p = f; q = a (Figure 2). Note that f 0(f ) = c0 cannot be used at any edge incident to v2 as d(v2; v6) = 1. Again, c0 cannot be used at any edge incident to v1 or v5 as f 0(a) = c0 + 1. Hence c0 cannot be used in the subgraph H0 isomorphic to H centering the triangle S10 = fv1; v2; v5g. In general, for any (p; q) pair in H, such a triangle can be found by considering the two triangles with common edge p and the two triangles with common edge q. Hence the proof.
Lemma 4. In the subgraph H, let the unused color c0 2= f5; 10g. Then, there must exist two disjoint pair of different typed edges (p; q) and (r; s) such that consecutive colors have been used in each pair of edges and p 2 Th; q 2 Ts ; r 2 Ts; s 2 Tv. Proof. Since, distance between any two edges in H is at most two, no color can be repeated. We need three sets of five different colors to color each type of edges in H. That means we need to divide the set of colors into three sets of equal size (i.e., five colors in each set) in such a way that we can maximize the number of sets that contain consecutive colors. We can say that the unused color divides the color set into two parts. By pigeon hole principle, we can show that either one part contains more than 10 consecutive colors or both of them contains more than five consecutive colors as the unused color c0 is neither 5 nor 10. In the former case, all three types of edges get color from the larger part of the colors as it contains more than 10 colors. In the later case, at least one type of edges get color from both the parts. So, in both the cases we get at least two such pairs.
edges and consecutive colors are assigned to p and q, at least 2 edges of E(G) n E(H) cannot be colored with the colors used in H.
Proof. We prove this Lemma using case analysis and the cases are based on where the edges p and q are present. Without loss of generality, we assume p 2 Th and q 2 Ts are colored with z and z + 1 respectively. We can have the following cases: – p; q 2 S3 : Without loss of generality, let p = f and q = c. From Lemma 3 it follows that if z is to be reused for 3 more times, then it has to be reused at edges of S5 incident to v1; v8 and v12, which is not possible since c is adjacent to v12. Similarly, if z + 1 is to be used for 3 more times, then it has to be reused at edges of S5 incident to v7; v2 and v4, which is also not possible since f is adjacent to v7. So, there are two edges in E(G) n E(H) which remain uncolored with the colors used in H. – p 2 S3; q 2 S2 : Without loss of generality, let p = h and q = e. From Lemma 3, if z is to be used for 3 more times, then it has to be reused at edges of S5 incident to v3, v10 and v11. But it is not possible since e is adjacent to v10. Similarly, if z + 1 is to be used for 2 more times, then it has to be reused at x5 = (v8; v11) of S4 and an edge of S5 incident to v1. It is not possible to use z + 1 at x5 as z is reused at an edge of S5 adjacent to v11. So, there are two edges in E(G) n E(H) which cannot be colored with the colors used in H. – p; q 2 S2 : Without loss of generality, let p = j and q = d. From Lemma 3, z is to be reused at x8 = (v1; v2) which is not possible here as edge d is adjacent to (v1; v2). Similarly, z + 1 is to be reused at x6 = (v4; v8) which is also not possible as edge j is adjacent to (v4; v8). Therefore, two edges at E(G) n E(H) cannot be colored with the colors used in H. – p 2 S1; q 2 S3 : Without loss of generality, let p = g and q = c. From Lemma 3 it follows that z has to be reused at x4. But here it is not possible as z + 1 used at c. If x4 is not left uncolored, then a color of H in fh; a; n; d; k; f g can only be used at that edge. If f 0(h) is used at x4, then f 0(h) can only be used at an edge of S5 incident to v3 but not at the edges of S5 incident to v10 and v11. So, in that case two edges will remain uncolored. If f 0(n) is used at x4, then f 0(n) can neither be used at x2 nor be used at an edge of S5 incident to v11. So, in that case too, two edges will remain uncolored. All other possibilities are symmetric to one of these two cases.
We now consider the case when the unused color, say u of H is used at x4. Since u cannot be used at v8 and v10, colors of fd; k; f; eg must be reused at the edges fx6; y12; y11; x5g and the colors of fn; a; h; og must be reused at the edges fx2; y3; y4; x3g. If f 0(i) and f 0(j) are reused at x9 and x8 respectively, then the edges where colors f 0(i) 1 and f 0(j) 1 can be used are ff; gg and fg; hg respectively. Therefore, if both f 0(i) and f 0(j) are reused at x9 and x8 respectively, then f 0(g) 1 = z 1 can only be used at fi; jg. Since z + 1 is used at c, either f 0(i) cannot be reused at x9 or f 0(j) cannot be reused at x8. Hence the unused color u of H has to be used at x9 or x8. Hence two edges at E(G) n E(H) cannot be colored with the colors used in H.
Now we will look at the difference of colors in the edges incident to same vertex. Initially we investigate the case when the difference is at least three for every pair. Then we consider the case when there exists at least a pair of edges with difference exactly two. We classify the six edges incident to the same vertex as follows. We say two such edges are at 60 if one is the immediate next edge of the other in clockwise or anticlockwise direction. They are said to be at 120 and 180 if exactly one and two edges respectively is/are there in between them. Now we subdivide the second case into three more cases depending on the angle between them.
Lemma 6. If jf 0(e1) then 02;1(T6) 16.
f 0(e2)j
Proof. Let us consider the edge g = (v5; v6) and without loss of generality assume f 0(g) = 0. To keep 02;1(T6) below 16, the colors that can be used at the remaining five incident edges of v5 are 3, 6, 9, 12 and 15. Now the least color that can be used at any of the five edges incident to v6 is 4. Therefore, the colors that can be used to the remaining four edges incident to v6 are 7, 10, 13 and 16 respectively. Hence 02;1(T6) 16. jc1
Therefore there exists at least two adjacent edges in T6 having color c1 and c2 with c2j = 2.
at an angle 60 in T6, then 02;1(T6) 16. Proof. Without loss of generality, assume f 0(b) = c0 and f 0(g) = c0 + 2. Observe that c0+1 must remain unused in H as 8e1 2 E(H)nfb; gg either d(e1; b) = 1 or d(e1; g) = 1. From Lemma 4 and Lemma 5, there are 4 edges in E(G) n E(H) which cannot be colored with colors used in H. To make 02;1(G) below 16, c0 + 1 is to be used in those 4 edges. Without loss of generality, assume c0 + 1 has been used at the edges incident to v1, v3, v8 and v12 respectively. Note that f 0(g) = c0 + 2 cannot be used at x4 as c0 + 1 is used at an edge incident to v12. So, f 0(x4) 2 ff 0(a); f 0(h); f 0(n); f 0(d); f 0(f ); f 0(k)g. Consider the case when f 0(x4) 2 ff 0(a); f 0(h); f 0(n)g as the case when f 0(x4) 2 ff 0(d); f 0(f ); f 0(k)g can be proved similarly. Assume f 0(x4) = f 0(a). There are four edges of S4 [ S5 incident to v10 where f 0(a), f 0(h), f 0(n) and f 0(o) can only be used. But f 0(a) cannot be used there as f 0(x4) = f 0(a). To make 02;1(G) below 16, f 0(x3) = c0 + 1 and f 0(n), f 0(h) and f 0(o) are assigned to the other three edges. Similarly, there are four edges of S4 [ S5 incident to v2 where f 0(i), f 0(c), f 0(m) and f 0(j) can only be used. Now observe that f 0(b) = c0 cannot be used at x1 as c0 + 1 is used at an edge incident to v3. Again, ff 0(n); f 0(h); f 0(o)g and ff 0(i); f 0(c); f 0(m); f 0(j)g cannot be used at x1 as they are used at edges incident to v10 and v2 respectively. Hence f 0(x1) = f 0(a). Proceeding similarly we can show that f 0(x9) = f 0(i), f 0(x8) = f 0(j), f 0(x7) = f 0(l) and f 0(x5) = f 0(e). Now observe that f 0(a) and f 0(x) are used at two adjacent vertices for all x 2 E(H) n fdg. Therefore one of f 0(a) 1 cannot be used in H. Moreover, none of f 0(a) 1 can be the unused color c0 + 1 as c0 and c0 + 2 are used at b and g respectively. Hence 02;1(G) 16.
at an angle 120 in T6, then 02;1(T6) 16.
Proof. Without loss of generality, assume f 0(g) = c0 and f 0(e) = c0 + 2 (Figure 2). There may be two cases, when c0 + 1 is used in H and when c0 + 1 is not used in H. First consider the second case. From Lemma 4, there are 4 edges in E(G) n E(H) which cannot be colored with the colors used in H. To make 02;1(G) below 16, c0 + 1 is to be used in those 4 edges. Without loss of generality, assume c0 + 1 is used in edges in E(G) n E(H) adjacent to vertices v1; v3; v8 and v12 respectively. Note that f 0(x4) 6= f 0(g) = c0 as c0 + 1 is used in an edge adjacent to v12. Therefore f 0(x4) 2 ff 0(a); f 0(h); f 0(n); f 0(d); f 0(f ); f 0(k)g. Let f 0(x4) = f 0(d). The color of four edges in S4 [ S5 incident to v8 are c0 + 1 and any three of f 0(d); f 0(e); f 0(f ) and f 0(k). But f 0(e) cannot be used there as f 0(e) = c0 + 2; f 0(d) cannot be used there as f 0(x4) = f 0(d). Hence a new color must be introduced here resulting 02;1(T6) 02;1(G) 16. Similar result holds when f 0(x4) 2 ff 0(f ); f 0(k)g. Now let us consider the case when f 0(x4) 2 ff 0(a); f 0(h); f 0(n)g. Let us consider f 0(x4) = f 0(a). Here the colors of four edges in S4 [S5 incident to v12 are c0 +1; f 0(h); f 0(n) and f 0(o). Therefore f 0(d); f 0(f ) and f 0(k) must be used at three edges incident to v12. As, f 0(e) = c0 + 2 cannot be used at any edge incident to v8 due to usage of c0 +1 at v8, any one of f 0(d); f 0(f ) and f 0(k) must be used in x5. But it is not possible as f 0(d); f 0(f ) and f 0(k) are used in edges adjacent to v12. Hence another color must be introduced here resulting 02;1(T6) 02;1(G) 16. Similar argument holds when f 0(x4) 2 ff 0(h); f 0(n)g. Hence the proof for this case.
Now we consider the case when f 0(g) = c0, f 0(e) = c0 + 2 and c0 + 1 is used in H. Let us consider a color c00 2 C = f0; 1; ; 15g n fc0; c0 + 1; c0 + 2g is unused in H. Without loss of generality, say c00 = c0 + 5. For any other color c00 in C we can prove the same result with similar arguments. From Lemma 4, c0 + 5 must be used in 4 edges of S4 [ S5 in E(G) n E(H). Here we assume c0 + 5 is used in 4 edges adjacent to the vertices v1; v3; v8 and v12 respectively. Since f (g) = c0, c0 1 can only be used in fc; i; j; mg. Let us consider f 0(j) = c0 1. The three edges h, f and i in Th are to be colored. Here we assume exactly two distinct pair of different types of edges (p; q) and (r; s) are assigned consecutive colors such that p 2 Th; q 2 Ts and r 2 Th; s 2 Tv. In that case c0 2, c0 3 and c0 4 must be assigned to edges in Th in H. Let us consider f 0(j) = c0 1. Now if f 0(m) = c0 + 1, then two edges j and m at 60 have colors c0 1 and c0 + 1 and from theorem 1, 02;1(T6) 16. Again f 0(i) 6= c0 + 1 as f 0(e) = c0 + 2. Therefore f 0(c) = c0 + 1. If f 0(b) = c0 + 3, then neither c0 + 4 nor c0 + 6 can be used at the edge a as c0 + 5 is used at an edge incident to v1. Hence f 0(a) = c0 + 3. Similarly we can show that f 0(d) = c0 + 4 and f 0(b) = c0 + 6. As c0 + 5 is used at an edge in S4 [ S5 incident to v12, at least any three among f 0(a); f 0(h); f 0(n) and f 0(o) must be assigned to the edges of S4 [ S5 incident to v10. Note that f 0(a) = c0 + 3 and f 0(e) = c0 + 2. Therefore f 0(a) cannot be assigned to an edge incident to v10. In that case f 0(h) and f 0(i) cannot be consecutive. So we get f 0(h) = c0 2, f 0(f ) = c0 3 and f 0(i) = c0 4. With similar argument we can show that f 0(o) = c0 5; f 0(m) = c0 6; f 0(k) = c0 7; f 0(n) = c0 8 and f 0(l) = c0 9. Now consider the edges of S4 [S5 incident to v8. Only f 0(d); f 0(e); f 0(f ) and f 0(k) can be used at edges of S4 [ S5 incident to v8. Note that f 0(d) = c0 + 4 cannot be used there because c0 + 5 is used at an edge of S5 incident to v8. Therefore f 0(k) = c0 7; f 0(f ) = c0 3 and f 0(e) = c0+2 must be used at edges in S4[S5 incident to v8. Now f 0(x5) 6= f 0(k) = c0 7 as f 0(m) = c0 6. If f 0(x5) = f 0(f ) = c0 3, then two edges j and x5 at 60 have colors c0 1 and c0 3 and from theorem 1, 02;1(T6) 16. Hence f 0(x5) = f 0(e) = c0 + 2. Since either f 0(y11) = c0 + 5 or f 0(y12) = c0 + 5 we get either f 0(x6) = c0 3 or f 0(x6) = c0 7. In both cases two edges o and x6 residing at an angle 60 have colors (c0 5; c0 3) or (c0 5; c0 7). Hence from theorem 1 02;1(T6) 16. When more than two distinct pair of different types of edges are assigned consecutive colors, arguing similarly, we can prove the same result. Hence the proof.
at an angle 180 in T6, then 02;1(T6) 16.
Proof. Without loss of generality, assume f 0(g) = c0 and f 0(h) = c0 + 2 (Figure 2). There may be two cases, when c0 + 1 is used in H and when c0 + 1 is not used in H. First assume c0 + 1 is used in H. Let us consider a color c00 2 C = f0; 1; ; 15g n fc0; c0 + 1; c0 + 2g is unused in H and it is used at the edges of S4 [ S5 in E(G) n E(H) adjacent to v1; v3; v8 and v12. Without loss of generality, say c00 = c0 + 7. For any other color c00 in C we can prove the same result with similar arguments. Both the colors c0 1 must be used at edges in H incident to v9. To make 02;1(G) less than 16, the two colors must be used at two edges at 180 incident to v9 otherwise from theorem 1 or theorem 2, 02;1(T6) 16. So, we assume f 0(j) = c0 + 1 and f 0(i) = c0 1. Similarly, f 0(f ) = c0 2. The color c0 3 can be used at an edge adjacent to v5. Let us consider f 0(n) = c0 3. Therefore, f 0(m) = c0 4; f 0(k) = c0 5; f 0(o) = c0 6 and f 0(l) = c0 7. Similarly, it can be shown that f 0(d) = c0 + 3; f 0(c) = c0 + 4; f 0(a) = c0 + 5; f 0(e) = c0 + 6 and f 0(b) = c0 + 8. Now observe that f 0(c), f 0(m), f 0(i) = c0 1 and f 0(j) = c0 + 1 must be used at the edges at S4 [ S5 incident to v2 as the unused color c00 is not used here. This implies f 0(j) = c0 + 1 and f 0(i) = c0 1 must be used at two edges in S4 [ S5 incident to v2 which are at 180 , as otherwise from theorem 1 or theorem 2, 02;1(T6) 16. Hence c0 + 1 and c0 1 must be used at x8 and x9. Now notice that f 0(d) = c0 + 3 and the edge d is at 60 and 120 with x9 and x8 respectively. Hence at v2, (c0 + 1; c0 + 3) must be used at two edges either at 60 or at 120 resulting 02;1(T6) 16 from theorem 1 or theorem 2.
Now consider the case when f 0(g) = c0; f 0(h) = c0 + 2 and c0 + 1 is not used in H. Assume c0+1 is used at four edges incident to v1; v3; v8 and v12. Note that c0 1 must be used at an edge incident to v9 in H. Here we assume exactly two distinct pair of different types of edges (p; q) and (r; s) are assigned consecutive colors such that p 2 Th; q 2 Ts and r 2 Th; s 2 Tv. Consider f 0(j) = c0 1. So, f 0(f ) = c0 2 otherwise c0 and c0 2 must be at two adjacent edges at an angle 60 or 120 . Note that either f 0(i) = c0 3 or f 0(i) = c0 + 3. First we assume f 0(i) = c0 + 3. In that case c0 + 4 can only be used at an edge incident to v6 in H, as otherwise c0 + 2 and c0 + 4 will be at two edges at an angle 60 or 120 . So, f 0(d) = c0 + 4. Therefore, f 0(a) = c0 + 5; f 0(c) = c0 + 6; f 0(e) = c0 + 7 and f 0(b) = c0+8. Similarly, f 0(n) = c0 3; f 0(m) = c0 4; f 0(k) = c0 5; f 0(o) = c0 6 and f 0(l) = c0 7. Note that any three among f 0(d); f 0(e); f 0(f ) and f 0(k) must be used at S4 [ S5 incident to v8 as c0 + 1 is used here. But f 0(f ) = c0 2 and f 0(k) = c0 5 cannot be used there as f 0(j) = c0 1 and f 0(o) = c0 6. Hence one more color must be introduced here resulting 02;1(T6) 02;1(G) 16. Similar argument holds when f 0(i) = c0 3. Hence the proof.
Till now we have considered the case when in H, the unused color cu 2= f5; 10g. Now we consider the case when cu 2 f5; 10g and the case when there is no unused color in H.
16.
Proof. Without loss of generality let us assume color 5 is unused in H. The set of colors f0; 1; ; 4g must be used in same type of edges and same holds for the sets f6; 7; ; 10g and f11; 12; ; 15g otherwise there exists at least two disjoint pair of edges (p; q) and (r; s) where consecutive colors are used in each pair and there we can prove 02;1(T6) 16 using similar argument as depicted in Lemma 6 and Theorem 1 or 2 or 3. Let us consider p = f; q = a; f 0(p) = c0 and f 0(q) = c0 + 1. From Observation 6, c0 cannot be used in the subgraph H0 isomorphic to H centering S10 = fv1; v2; v5g. If c0 6= 10, then from Theorem 1 or 2 or 3 02;1(T6) 16. If c0 = 10 then f 0(q) = c0 + 1 = 11. In that case the colors f0; 1; ; 4g must be used in Tv, f6; 7; ; 10g must be used in Th and f11; 12; ; 15g must be used in Ts. From Observation 4, the edges for reusing f 0(f ) = c0 = 10 are y5; y12; y16 and (u3; u4). If f 0(f ) = c0 = 10 is used at (u3; u4), then f 0(a) = c0 + 1 = 11 cannot be used at its opposite edge y21 and hence from Observation 4, Lemma 6 and Theorem 1 or 2 or 3 02;1(T6) 16. If f 0(f ) = c0 = 10 is not used at (u3; u4), then either color 5 or a color c00 6= f5; 10g used in H must be used there. If a color c00 is used there, then there exists a pair of opposite edges where c00 cannot be used and again from Observation 4, Lemma 6 and Theorem 1 or 2 or 3 02;1(T6) 16. So, to keep 02;1(T6) below 16, color 5 must be used at (u3; u4). With exactly same argument we can show that color 5 must also be used at y5; y12; y16 otherwise 02;1(T6) 16. Remember that the color 4 is used in Tv and it must also be used at its opposite edges. Note that for any edges e1 2 Tv n fmg, either e1 or its opposite edge is adjacent to an edge e2 where f (e2) = 5. Hence f 0(m) = 4. But y13, the opposite edge of m, cannot have color 4 as color 5 is used at y12. Hence from Observation 4, Lemma 6 and Theorem 1 or 2 or 3 02;1(T6) 16.
; 14g are used at H, then 02;1(T6) 16.
Proof. In this case there exists a pair of different types of edges in H where (c0; c0 + 1) are used. From Observation 6, there exists a H0 isomorphic to H where c0 or c0 + 1 cannot be used. Hence either from Theorem 4 or from Lemma 6 and Theorem 1 or 2 or 3, it follows that 02;1(T6) 16. 3
Lemma 7. 20;1(T6) 18
17 13 15 12 14 16 13 8 0 7 1 6 2 10 3 9 4 8 0 7
12 14 16 13 15 12 10 1 9 2 8 3 7 4 6 0 10 1 9
16 13 15 12 14 16 7 2 6 3 10 4 9 0 8 1 7 2 6
15 12 14 16 13 15 9 3 8 4 7 0 6 1 10 2 9 3 8
14 16 13 15 12 14 6 4 10 0 9 1 8 2 7 3 6 4 10
13 15 12 14 16 13 8 0 7 1 6 2 10 3 9 4 8 0 7 12 14 16 13 15 12
17 Proof. In this grid there are three types of edges- horizontal, vertical and slanted. In order to proof the Lemma, we now consider the labeling shown in Figure 3. Assuming left bottom corner point as origin, the labeling functions corresponding to horizontal, vertical and slanted edges can be stated as:
f 0((x; y); (x + 1; y)) = (7x + y) mod 5 + 12 f 0((x; y); (x; y + 1)) = (3y
x + 2) mod 5 + 6 f 0((x 1; y + 1); (x; y)) = (x + 4y . Observe that different types of edges get different colors in the coloring. Horizontal edges get color 12; 13; 14; 15; 16; vertical edges get 6; 7; 8; 9; 10 and slanted edges get 0; 1; 2; 3; 4. By the pattern it is clear that two adjacent edges of same type do not get two consecutive colors. By the definition of n-circular-L(2; 1)-edge labeling 0 and n are two consecutive colors. In our coloring there are many places where two adjacent edges get 0 and 16. So, the color 16 cannot be the circular span of the grid. That’s why we introduce a new color 17, which is used at edges as a replacement for 16 such that 0 and 16 become two non-consecutive colors. Two such 16 colored edges are shown in Figure 3 whose colors can be replaced by 17. Putting 17 at any one such edge is sufficient. The main goal behind introducing a new color 17 was to make 0 and 16 non-consecutive. As the colors 5 and 11 are unused in the graph, we can conclude that no two adjacent edges of different types get two consecutive colors. Now we have to show that no two edges at distance two get the same color. For the same type of edges it can be easily followed from the pattern of repetition. In case of different type of edges, observe that distant two edges of two different types get color with difference at least two. Hence this labeling can be extended to infinite grid. 4
Here we prove the conjecture 02;1(T6) = 16 given by Lin and Wu [