Open Journal of Discrete Applied Mathematics

On graceful difference labelings of disjoint unions of circuits

Alain Hertz1, Christophe Picouleau
Department of Mathematics and Industrial Engineering, Polytechnique Montréal and GERAD, Montréal, Canada.; (A.H)
CEDRIC, Conservatoire National des arts et métiers, Paris France.; (C.P)
1Corresponding Author: alain.hertz@gerad.ca

Abstract

A graceful difference labeling (gdl for short) of a directed graph G with vertex set V is a bijection f:V{1,,|V|} such that, when each arc $uv$ is assigned the difference label f(v)f(u), the resulting arc labels are distinct. We conjecture that all disjoint unions of circuits have a gdl, except in two particular cases. We prove partial results which support this conjecture.

Keywords:

Graceful labelings, directed graphs, disjoint unions of circuits.

1. Introduction

A graph labeling is the assignment of labels, traditionally represented by integers, to the vertices or edges, or both, of a graph, subject to certain conditions. As mentioned in the survey by Gallian [1], more than one thousand papers are devoted to this subject. Among all variations, the most popular and studied graph labelings are the β-valuations introduced by Rosa in 1966 [2], and later called graceful labelings by Golomb [3]. Formally, given a graph G with vertex set V and q edges, a graceful labeling of G is an injection f:V{0,1,,q} such that, when each edge uv is assigned the label |f(v)f(u)|, the resulting edge labels are distinct. In other words, the vertices are labeled using integers in {0,1,,q}, and these vertex labels induce an edge labeling from 1 to q. The famous Ringel-Kotzig conjecture, also known as the graceful labeling conjecture, hypothesizes that all trees are graceful. It is the focus of many papers and is still open, even for some very restricted graph classes such that trees with 5 leaves, and trees with diameter 6. The survey by Gallian [1] lists several papers dealing with graceful labelings of particular classes of graphs, such that the disjoint union of cliques, the disjoint union of cycles, and the union of cycles with one common vertex.

For a directed graph with vertex set V and q edges, a graceful labeling of G is an injection f:V{0,1,,q} such that, when each arc (i.e., directed edge) uv is assigned the label (f(v)f(u)) (mod q+1), the resulting arc labels are distinct. As mentioned in [1] and [4], most results and conjectures on graceful labelings of directed graphs concern directed cycles, the disjoint union of directed cycles, and the union of directed cycles with one common vertex or one common arc. In particular, it is proved that nC3, the disjoint union of n copies of the directed cycle with three vertices, has a graceful labeling only if n is even. However, it is not known whether this necessary condition is also sufficient.

In this paper, we study graceful difference labelings of directed graphs, which are defined as follows. A graceful difference labeling (gdl for short) of a directed graph G=(V,A) is a bijection f:V{1,,|V|} such that, when each arc uv is assigned the difference label f(v)f(u), the resulting arc labels are distinct. The absolute value |f(v)f(u)| is called the magnitude of arc uv, while f(v) is the vertex label of v. Note that in a gdl of G, two arcs uv and uv may have the same magnitude |f(v)f(u)|=|f(v)f(u)| but their difference labels must then be opposite, i.e., f(v)f(u)=(f(v)f(u)).

Given two graphs Gi=(Vi,Ai) and Gj=(Vj,Aj) with ViVj=, their disjoint union, denoted Gi+Gj, is the graph with vertex set ViVj and arc set AiAj. By pG we denote the disjoint union of p copies of G. For k2 we denote by Ck a circuit on k vertices isomorphic to the directed graph with vertex set V={v1,,vk} and arc set A={vivi+1: 1i<k}{vkv1}. The circuit C3 is also called a directed triangle, or simply a triangle. For all graph theoretical terms not defined here the reader is referred to [5].

Not every directed graph has a gdl. Indeed, a necessary condition for G=(V,A) to have a gdl is |A|2(|V|1). Nevertheless this condition is not sufficient since, for example, C3 has no gdl. Indeed, all bijections f:V{1,2,3} induce two difference labels equal to 1, or two equal to -1. As a second example, C2+C3 has no gdl. Indeed:

  • If the two arcs of C2 have a magnitude equal to 1, 2, or 3, then C3 also has an arc with the same magnitude, which means that two arcs in C2+C3 have the same difference label;
  • If the magnitude of two arcs of C2 is equal to 4, then two difference labels in C3 are equal to 1 or to -1.

We conjecture that all disjoint unions of circuits have a gdl, except for the two cases mentioned above. We were not able to prove this conjecture, but give partial results on it. In particular, we show that nC3 has a gdl if and only if n2.

2. Partial proof of the conjecture

We are interested in determining which disjoint unions of circuits have a gdl. As already mentioned in the previous section, C3 and C2+C3 have no gdl. We conjecture that these two graphs are the only two exceptions. As first result, we show that if G is a circuit of length k=2 or k4, then G has a gdl. We next prove that if G has a gdl, and if G is obtained by adding to G a circuit of even length k=2 or k6, or two disjoint circuits of length 4, then G also has a gdl. We also show that the disjoint union of C4 with a circuit of odd length has a gdl. All together, these results prove that if G is the disjoint union of circuits, among which at most one has an odd length, then G has a gdl, unless G=C3 or G=C2+C3.

We next show that the disjoint union of n2 circuits of length 3 has a gdl, and this is also the case if a C4 is added to nC3. Hence, if G is the union of disjoint circuits with no odd circuit of length k5, then G has a gdl, unless G=C3 or G=C2+C3. In order to prove the above stated conjecture, it will thus remain to show that if G is the disjoint union of circuits with at least two odd circuits, among which at least one has length k5, then G has a gdl.

Our first lemma shows that all circuits have a gdl, except C3.

Lemma 1. The circuit Ck with k=2 or k4 has a gdl. Moreover, if k5, then Ck has a gdl with exactly one arc of magnitude 1.

Proof. Clearly, C2 has a gdl since the two bijections f : V{1,2} have 1 and 1 as difference labels. So assume k4. We distinguish four cases, according to the value of kmod4:

  • If k=4p,p1, we consider the following vertex labels:
    • f(v2i+1)=i+1,0i2p2;
    • f(v2i)=4p+1i,1i2p2;
    • f(v4p2)=2p+1, f(v4p1)=2p+2, f(v4p)=2p.
    Clearly, f is a bijection between {v1,,vk} and {1,,k} with the following difference labels:
    • f(vi+1)f(vi)=(1)i+1(4pi),1i4p4;
    • f(v4p2)f(v4p3)=2, f(v4p1)f(v4p2)=1, f(v4p)f(v4p1)=2, f(v1)f(v4p)=2p+1.
    All magnitudes are distinct, except in three cases:
    • f(v4p2)f(v4p3)=2 and f(v4p)f(v4p1)=2;
    • for p3, f(v2p+2)f(v2p+1)=2p1 and f(v1)f(v4p)=(2p1);
    • for p=1, f(v4p1)f(v4p2)=1 and f(v1)f(v4p)=1.
    Hence, f is a gdl, and there is exactly one arc of magnitude 1 when p2.
  • If k=4p+1,p1, we consider the following vertex labels:
    • f(v2i+1)=i+1,0i2p;
    • f(v2i)=4p+2i,1i2p.
    Again, f is a bijection between {v1,,vk} and {1,,k} with the following difference labels:
    • f(vi+1)f(vi)=(1)i+1(4p+1i),1i4p;
    • f(v1)f(v4p+1)=2p.
    All magnitudes are distinct, except for one pair of arcs : f(v2p+2)f(v2p+1)=2p and f(v1)f(v4p+1)=2p. Hence, f is a gdl with exactly one arc of magnitude 1.
  • If k=4p+2,p0, we consider the following vertex labels:
    • f(v2i+1)=i+1,0i2p;
    • f(v2i)=4p+3i,1i2p+1.
    Here also, f is a bijection between {v1,,vk} and {1,,k} with the following difference labels:
    • f(vi+1)f(vi)=(1)i+1(4p+2i),1i4p+1;
    • f(v1)f(v4p+2)=2p1.
    There are only two equal magnitudes : f(v2p+2)f(v2p+1)=2p+1 and f(v1)f(v4p+2)=(2p+1). Hence, f is a gdl with exactly one arc of magnitude 1 when p1.
  • If k=4p+3,p1, we consider the following vertex labels:
    • f(v2i+1)=i+1,0i2p1;
    • f(v2i)=4p+4i,1i2p;
    • f(v4p+1)=2p+2, f(v4p+2)=2p+1, f(v4p+3)=2p+3.
    For this last case, f is a bijection between {v1,,vk} and {1,,k} with the following difference labels:
    • f(vi+1)f(vi)=(1)i+1(4p+3i),1i4p1;
    • f(v4p+1)f(v4p)=2, f(v4p+2)f(v4p+1)=1, f(v4p+3)f(v4p+2)=2, f(v1)f(v4p+3)=(2p+2).
    All magnitudes are distinct, except in two cases:
    • f(v4p2)f(v4p3)=2 and f(v4p)f(v4p1)=2;
    • f(v2p+2)f(v2p+1)=2p+2 and f(v1)f(v4p+3)=(2p+2).
    Hence, f is a gdl with exactly one arc of magnitude 1.

We now show how to add two circuits of length 4, or one even circuit of length k6 to a graph that has a gdl.

Lemma 2. If a graph G has a gdl, then G+2C4 also has a gdl.

Proof. Let {v1,v2,v3,v4} be the vertex set of the first C4, and let {v1v2,v2v3,v3v4,v4v1} be its arc set. Also, let {v5,v6,v7,v8} be the vertex set of the second C4, and let {v5v6,v6v7,v7v8,v8v5} be its arc set. Suppose G=(V,A) has a gdl f. Define f(v)=f(v)+4 for all vV as well as f(v1)=1,f(v2)=|V|+8,f(v3)=2,f(v4)=|V|+6,f(v5)=3,f(v6)=|V|+5,f(v7)=4, and f(v8)=|V|+7. Clearly, f is a bijection between V{v1,,v8} and {1,,|V|+8}. Moreover, the difference labels on the arcs of the two circuits are f(v2)f(v1)=|V|+7,f(v3)f(v2)=(|V|+6),f(v4)f(v3)=|V|+4,f(v1)f(v4)=(|V|+5),f(v6)f(v5)=|V|+2,f(v7)f(v6)=(|V|+1),f(v8)f(v7)=|V|+3, and f(v5)f(v8)=(|V|+4). Since all magnitudes in G are at most equal to |V|1, f is a gdl for G+2C4.

Note that in the proof of Lemma 2, G can be the empty graph G with no vertex and no arc. Hence 2C4 has a gdl.

Lemma 3. If a graph G has a gdl, then G+C2k also has a gdl for k1,k2.

Proof. Suppose G=(V,A) has a gdl f, and let {v1,,v2k} be the vertex set and {v1v2,,v2k1v2k,v2kv1} be the arc set of C2k. We consider two case.

  • If k is odd, then define f(v)=f(v)+k for all vV, as well as f(v2i1)=ki+1 and f(v2i)=|V|+k+i for 1ik. Clearly, f is a bijection between V{v1,,v2k} and {1,,|V|+2k}. Moreover, the magnitudes on C2k are all striclty larger than |V| and all different, except in one case : f(vk+1)f(vk)=|V|+k and f(v1)f(v2k)=(|V|+k). Since all magnitudes in G are strictly smaller than |V|, f is a gdl for G+C2k.
  • If k is even and at least equal to 4, then set f(v)=f(v)+k for all vV, and define the vertex labels on C2k as follows:
    • f(v2i1)=ki+1 for 1ik;
    • f(v2i)=|V|+k+i for 1ik3;
    • f(v2k4)=|V|+2k,f(v2k2)=|V|+2k2,f(v2k)=|V|+2k1.
    f is bijection between V{v1,,v2k} and {1,,|V|+2k}, and all magnitudes on C2k are strictly larger than |V|. Moreover, all magnitudes on C2k are different, except in two cases :
    • f(vk)f(vk1)=|V|+k1 and f(v1)f(v2k)=(|V|+k1);
    • f(v2k4)f(v2k5)=|V|+2k3 and f(v2k1)f(v2k2)=(|V|+2k3).
    Since all magnitudes in G are strictly smaller than |V|, f is a gdl for G+C2k.

Since graph G in the statement of Lemma 2 is possibly empty, it follows from Lemmas 1, 2 and 3 that all disjoint unions of circuits of even length have a gdl. We now consider disjoint unions of circuits among which exactly one has as an odd length. As already observed, C3 and C2+C3 have no gdl. We show that these are the only two exceptions. According to Lemmas 2 and 3, it is sufficient to prove that 2C2+C3, C4+C2k+1 (k1), and C2k+C3 (k3) have a gdl.

Lemma 4. 2C2+C3 has a gdl.

Proof. Let {v1,,v7} be the vertex set and {v1v2, v2v1, v3v4, v4v3, v5v6, v6v7, v7v5} be the arc set of 2C2+C3. By considering the vertex labels f(v1)=1, f(v2)=6, f(v3)=3, f(v4)=7, f(v5)=2, f(v6)=4 and f(v7)=5, it is easy to observe that f is a gdl.

Lemma 5. C4+C2k+1 has a gdl for every k1.

Proof. Let G=C4+C2k+1. We distinguish two cases:

  • If k is odd, then G contains n=4(k+12)+3 vertices. Consider the vertex labels of Cn used in the last case of the proof of Lemma 1, with p=k+12, and assume that {v1,vn2,vn1,vn} is the vertex set of the C4 in G, while {v2,v3,,vn3} is the vertex set of the C2k+1. It is sufficient to prove that the difference labels on v1vn2 and vn3v2 do not appear on any other arc of G.
    • f(vn2)f(v1)=(2p+2)1=(k+3)1=k+2, which is an odd positive number, while all other odd difference labels are negative.
    • f(v2)f(vn3)=(4p+3)(2p+4)=2p1=k, which is again an odd positive number, different for the other negative odd labels.
  • If k is even, consider the vertex labels of C2k+4 used in the first case of the proof of Lemma 1 with p=k2+12 (i.e., 4p=2k+4). Also, define f(v2k+5)=2k+5=4p+1. Assume that {v1,v2k+2,v2k+3,v2k+4} is the vertex set of the C4 in G, while {v2,v3,,v2k+1,v2k+5} is the vertex set of the C2k+1. It is sufficient to prove that the difference labels on v1v2k+2, v2k+5v2, and v2k+1v2k+5 do not appear on any other arc of G.
    • f(v2k+2)f(v1)=(2p+1)1=(k+3)1=k+2, which is an even positive number, while all other even difference labels are negative.
    • f(v2)f(v2k+5)=(4p)(4p+1)=1. Since p>1, the only other arc with magnitude 1 is v2k+2v2k+3 which has a difference label of 1.
    • f(v2k+5)f(v2k+1)=(4p+1)(2p1)=2p+2=k+4, which is again an even positive number, while all other even difference labels are negative.

Lemma 6. Ck+C3 has a gdl for every k5.

Proof. Let {v1,,vk+3} be the vertex set and {v1v2,,vk1vk, vkv1, vk+1vk+2, vk+2vk+3, vk+3vk+1} be the arc set of G=Ck+C3. Consider the gdl f defined in the proof of Lemma 1 for Ck, and set f(vi)=f(vi)+2 for all i=1,,k. If the only arc of magnitude 1 has a difference label equal to -1, then define f(vk+1)=1, f(vk+2)=2, and f(vk+3)=k+3, else define f(vk+1)=2, f(vk+2)=1, and f(vk+3)=k+3. Clearly, f is a bijection between {v1,,vk+3} and {1,,k+3}. To conclude that f is a gdl, it is sufficient to prove that the difference labels on C3 do not appear on Ck.

  • The arc vk+1vk+2 is of magnitude 1, and its difference label has the sign opposite to that of magnitude 1 in Ck;
  • The magnitudes of vk+2vk+3 and vk+3vk+1 are distinct and larger than k, while all magnitudes in Ck are strictly smaller than k.

All together, the previous lemmas show that if G be the disjoint union of circuits, among which at most one has an odd length, then G has a gdl if and only if GC3 and GC2+C3.

We now consider the disjoint union of n circuits of length 3, and show that these graphs have a gdl for all n2.

Lemma 7. For every n2, the graph nC3 has a gdl with at most one arc of magnitude 3n2, and all other arcs of magnitude strictly smaller than 3n2.

Proof. The graphs in Figures 1, 2, 3, 4, 5, 6, 7 and 8 show the existence of the desired gdl for 2n9.

Figure 1. 2C3.

Figure 2. 3C3

Figure 3. 4C3.

Figure 4. 5C3.

Figure 5. 6C3.

Figure 6. 7C3.

Figure 7. 8C3.

Figure 8. 9C3.

We now prove the result by induction on n. So, consider the graph nC3 with n10, and assume the result is true for less than n directed triangles. Let t and r be two integers such that 4r2 and n=7t+r.

We thus have t2. We will show how to construct a gdl for nC3 given a gdl for tC3. We thus have to add nt directed triangles to tC3. For this purpose, define θ=nt2=3t+r2.

It follows that nt=2θ if r is even, and nt=2θ1 if r is odd. We now prove the lemma by considering the 4 cases A,B,C,D defined in Table 1. \setlength{\doublerulesep}{\arrayrulewidth}

Table 1. Four different cases.
nt r θ Case
2θ -4 3t2 A
-2 3t1
0 3t
2 3t+1 B
2θ1 -3 3t1 C
-1 3t
1 3t+1 D

Case A : n=2θ+t, θ{3t2,3t1,3t} Consider 2θ directed triangles T1,,T2θ, every Ti having {v3i2,v3i1,v3i} as vertex set and {v3i2v3i1, v3i1v3i, v3iv3i2} as arc set. Consider the vertex labels f(vi) for T1,,T2θ shown in Table 2.
Table 2. The labeling of T1,,T2θ for case A.
Triangle Ti f(v3i2) f(v3i1) f(v3i)
T1 1 2θ 6θ+3t6
T2 2 6θ+3t3 4θ+3t2
T3 3 6θ+3t4 2θ+1
T4 4 4θ+3t1 6θ+3t2
T2k1 2k1 2θ+k 6θ+3t2k+2
T2k 2k 6θ+3t2k+1 4θ+3tk+1
k=3,,θ3

Also, let f be a gdl for tC3 with at most one arc of magnitude 3t2, and all other arcs of magnitude strictly smaller than 3t2. Define f(vi)=f(vi)+3θ for i=6θ+1,,6θ+3t. One can easily check that f is a bijection between the vertex set {v1,,v6θ+3t} and {1,,6θ+3t=3n}.

For each Ti, we define its small difference label (small-dl for short) as the minimum among |f(v3i1)f(v3i2)|, |f(v3i)f(v3i1)|, and |f(v3i2)f(v3i)|. Similarly, the big difference label (big-dl) of Ti is the maximum of these three values, and the medium one (medium-dl) is the third value on Ti. Table 3 gives the small, medium and big difference labels of T1,,T2θ. By considering two dummy directed triangles D1 and D2, we have grouped the triangles into θ+1 pairs π0,,πθ, as shown in Table 3. Two triangles belong to the same pair πi if their small difference labels have the same magnitude. The difference labels given for D1 and D2 are artificial, but are helpful for simplifying the proof.

Table 3. The difference labels of the arcs of T1,,T2θ,D1,D2 for case A.
Pair Triangle Small-dl Medium-dl Big-dl
π0=(T1,T2) T1 2θ 4θ+3t4 (6θ+3t4)
T2
2θ (4θ+3t2) 6θ+3t2
π1=(T3,T4) T3 (2θ1) (4θ+3t3) 6θ+3t4
T4 2θ1 4θ+3t5 (6θ+3t6)
π2=(D1,T5) D1 (2θ2) (4θ+3t5) 6θ+3t7
T5 2θ2 4θ+3t7 (6θ+3t9)
πk=(T2k,T2k+1) T2k (2θk) (4θ+3t3k+1) 6θ+3t4k+1
k=3,,θ1 T2k+1 θk 4θ+3t3k1 (6θ+3t4k1)
πθ=(T2θ,D2) T2θ θ (θ+3t+1) 2θ+3t+1
D2 θ θ+3t1 (2θ+3t1)
Let s1i be the small-dl of the first triangle of πi, and let s2i be the small-dl of the its second triangle. Define m1i, m2i, b1i and b2i in a similar way for the medium and big difference labels of πi. For example, s12=(2θ2), s22=2θ2, m12=(4θ+3t5), m22=4θ+3t7, b12=6θ+3t7, and b22=(6θ+3t9). Note that sji+mji=bji and |sji|+|mji|=|bji| for all i=0,,θ and j=1,2. The following properties are valid for every πi with 2iθ:
  • s1i, m1i and b2i are negative integers, while s2i, m2i and b1i are positive integers;
  • s2i=s1i, m2i=m1i2, and b2i=b1i+2;
  • if i<θ, then s1i+1=s1i+1, m1i+1=m1i+3, and b1i+1=b1i4.
Note that all big difference labels bji have the same parity for 2iθ, j=1,2, while for the medium ones, the parities alternate between successive πi and πi+1. Moreover, the largest magnitude is 6θ+3t2=3n2, and there is exactly one arc with this magnitude. Since θ<3t+1, we have θ+3t+1>2θ, which means that no medium-dl can be equal to a small-dl, with the exception of m2θ which can be equal to 2θ or 2θ1. But we don't care about this exception since D2 (the second triangle of πθ) is a dummy triangle. Notice also that the small difference labels in Table 3 are all distinct, which is also the case for the medium and the big ones. Since all difference labels on T2θ+1,,T2θ+t are distinct, we conclude that there are only two possibilities for two arcs uv and uv of nC3 to have the same difference label f(v)f(u)=f(v)f(u):
  • One of these arcs belongs to T2θ+1,,T2θ+t and the other to T_{1},\ldots,T_{2\theta};
  • Both arcs belong to T_{1},\ldots,T_{2\theta}, one having a big-dl, and the other a medium-dl.

Consider the first case. Remember that there is at most one arc on T_{2\theta+1},\ldots,T_{2\theta+t} with magnitude 3t-2, all other arcs having a smaller magnitude. Since at most one arc on T_{1},\ldots,T_{2\theta} has a magnitude equal to \theta\geq 3t-2, we conclude that such a situation can only occur at most once (with \theta=3t-2), and we can avoid it by flipping all triangles T_{2\theta+1},\ldots,T_{2\theta+t}.

More precisely, by flipping a directed triangle \overrightarrow{C_3} with vertex set \{x,y,z\} and arc set \{xy,yz,zx\}, we mean exchanging the vertex labels of y and z. Hence, the set of difference labels is modified from \{f(y)-f(x), f(z)-f(y), f(x)-f(z)\} to \{f(z)-f(x), f(y)-f(z), f(x)-f(y2)\}, which means that each difference label of the original set appears with an opposite sign in the modified set, but with the same magnitude.

Consider the second case, and let i and j be such that b^x_{i}=m^y_{j} for x,y in \{1,2\}.

Note that 0\leq j < i \leq \theta. We say that \pi_i is conflicting with \pi_j and we write \pi_i\rightarrow \pi_j. If \pi_i is not conflicting with \pi_j, we write \pi_i\nrightarrow \pi_j. Note that

\begin{equation}\label{a} \text{if there are } k< j< i \text{ such that }\pi_i\rightarrow \pi_j\rightarrow \pi_k, \text{ then }\pi_k\nrightarrow \pi_{\ell}\text{ for all }\ell< k. \end{equation}
(1)

Indeed, if \pi_i\rightarrow \pi_j\rightarrow \pi_k, then there are x,y,z,w in \{1,2\} such that b^x_i=m^y_j and b^z_j=m^w_k. Then: |b^w_k|=|m^w_k|+|s^w_k|=|b^z_j|+|s^w_k|\geq|b^y_j|+|s^w_k|-2=|m^y_j|+|s^y_j|+|s^w_k|-2=|b^x_i|+|s^y_j|+|s^w_k|-2.

Since |b^x_i|\geq 2\theta+3t+1, |s^w_k |> |s^y_j|> |s^x_i|\geq\theta, we have \min\{|b^1_k|,|b^2_k|\}\geq|b^w_k|-2\geq4\theta+3t. Hence, \pi_k\nrightarrow \pi_{\ell} for all \ell< k since there is no arc with medium magnitude at least equal to 4\theta+3t.

We now show how to avoid conflicting pairs \pi_i and \pi_j with both i and j at least equal to 2. Conflicts involving \pi_0 and \pi_1 (i.e., T_{1},\ldots,T_{4}) will be handled later. Consider i and j such that 2\leq j< i< \theta and \pi_i\rightarrow \pi_j. Since b^1_i and m^2_j are positive, while b^2_i and m^1_j are negative, we either have b^1_i=m^2_j or b^2_i=m^1_j. In the first case, we say that \pi_i is 12-conflicting with \pi_j, while in the second case, we say that \pi_i is 21-conflicting with \pi_j. Note that

\begin{equation}\label{b} \text{if }\pi_i\text{ is }12-\text{conflicting with }\pi_j\text{, then }\pi_{i-1}\text{ is }21-\text{conflicting with }\pi_j\text{ and }\pi_{i+1}\nrightarrow \pi_j. \end{equation}
(2)
\begin{equation}\label{c} \text{if }\pi_i\text{ is }21-\text{conflicting with }\pi_j\text{, then }\pi_{i+1}\text{ is }12-\text{conflicting with }\pi_j\text{ and }\pi_{i-1}\nrightarrow \pi_j. \end{equation}
(3)

Indeed, if \pi_i is 12-conflicting with \pi_j, then b^1_i=m^2_j, which implies b^2_{i-1}\!=\!-b^1_i\!-\!2\!=\!-m^2_j\!-\!2\!=\!m^1_j. Since \max\{|b^1_{i+1}|,|b^2_{i+1}|\}=|b^1_{i+1}|=b^1_i-4< m^2_j\leq \min\{|m^1_j|,|m^2_j|\}, we have \pi_{i+1}\nrightarrow \pi_j.

Similarly, if \pi_i is 21-conflicting with \pi_j, then b^2_i=m^1_j, which implies b^1_{i+1}\!=\!-b^2_i\!-\!2\!=\!-m^1_j\!-\!2\!=\!m^2_j. Moreover, since \min\{|b^1_{i-1}|,|b^2_{i-1}|\}=|b^2_{i-1}|=|b^2_i|+4>m^1_j= \max\{|m^1_j|,|m^2_j|\}, we have \pi_{i-1}\nrightarrow \pi_j. Observe also that:
\begin{equation}\label{d} \text{if }\pi_i\rightarrow \pi_j\text{ for }2\leq j\text{, then }\pi_k\nrightarrow \pi_j\text{ for }2\leq k\neq i,i-1,i+1. \end{equation}
(4)
Indeed, if 2\leq k< i-1, then \min\{|b^1_k|,|b^2_k|\}\geq\max\{|m^1_j|,|m^2_j|\}+4, while for \theta\geq k>i+1, we have \max\{|b^1_k|,|b^2_k|\}\leq\min\{|m^1_i|,|m^2_i|\}-4. In both cases, none of m^1_j and m^2_j can be equal to b^1_k or b^2_k. As next property, note that:
\begin{equation}\label{e} \text{if }\pi_i\rightarrow \pi_j\text{ for }2\leq j\text{, then }\pi_i\nrightarrow \pi_k\text{ for }1\leq k \neq j. \end{equation}
(5)

Indeed, let us first show that \pi_i\nrightarrow \pi_{j-1}. If j=2, then m^1_1\!=\!m^1_2\!-\!2\!=\!-\!m^2_2\!-\!4 and m^2_1\!=\!-m^1_2\!=\!m^2_2\!+\!2. Since we have either b^1_i=m^2_2 and b^2_i=-m^2_2+2, or b^2_i=m^1_2 and b^1_i=-m^1_2+2, we see that \pi_i\nrightarrow \pi_1. For j>2, observe that b^1_i,b^2_i,m^1_j,m^2_j all have the same parity, while m^1_{j-1},m^2_{j-1} have the opposite parity. Hence \pi_i\nrightarrow \pi_{j-1}.

Similarly, \pi_i\nrightarrow \pi_{j+1} for all 2\leq j \leq \theta-1 since the parity of m^1_{j+1},m^2_{j+1} is the opposite of the parity of b^1_i,b^2_i.

Now, let x,y\in\{1,2\} be such b^x_i=m^y_j. If 1\leq k< j-1, then \min\{|m^1_k|,|m^2_k|\}\geq\max\{|b^1_i|,|b^2_i|\}+2, while for \theta\geq k>j+1, \max\{|m^1_k|,|m^2_k|\}\leq\min\{|b^1_i|,|b^2_i|\}-2.

In both cases, none of m^1_k and m^2_k can be equal to b^1_i or b^2_i, which proves that \pi_i\nrightarrow \pi_{k} for k\geq 1, k\neq j-1,j,j+1.

In what follows, we will remove conflicts by flipping some triangles. More precisely, by flipping \pi_i, we mean flipping both triangles in \pi_i. Note that:
\begin{equation}\label{f} \text{if }\pi_i\rightarrow \pi_j\text{ for }j\geq 2\text{, then }\pi_i\nrightarrow \pi_k\text{ for all }k\geq 2\text{ after the flip of }\pi_i. \end{equation}
(6)
Indeed, if \pi_i is 12-conflicting with \pi_j, then b^1_i=m^2_j, and there is no triangle with medium-dl equal to -b^1_i=-m^2_j= or -b^2_i=b^1_i-2=m^2_j-2. Similarly, if \pi_i is 21-conflicting with \pi_j, then b^2_i=m^1_j, and there is no triangle with medium-dl equal to -b^1_i=-b^2_i+2=-m^1_j+2 or -b^2_i=-m^1_j. Hence, we have \pi_i\nrightarrow \pi_k for all k\geq 2 after the flip of \pi_i. Also,
\begin{equation}\label{g} \text{if }\pi_i\rightarrow \pi_j\text{ for }j\geq 2\text{, then }\pi_k\nrightarrow \pi_j\text{ for all }k\leq \theta\text{ after the flip of }\pi_j. \end{equation}
(7)

Indeed, if \pi_i is 12-conflicting with \pi_j, then b^1_i=m^2_j, b^2_{i-1}=m^1_j, and there is no triangle with a big-dl equal to -m^1_j=-b^2_{i-1} or -m^2_j=-b^1_i. Similarly, if \pi_i is 21-conflicting with \pi_j, then b^2_i=m^1_j, b^1_{i+1}=m^2_j, and there is no triangle with a big-dl equal to -m^1_j=-b^2_{i} or -m^2_j=-b^1_{i+1}. Hence, we have \pi_k\nrightarrow \pi_j for all k\leq \theta after the flip of \pi_j.

Now, let J be the set of integers j such that \pi_i\rightarrow \pi_j\rightarrow \pi_k for at least one pair i,k of integers with 2\leq k< j< i\leq \theta. Also, let J' be the set of integers j' such that there is k\geq 2 and j\neq j' in J with \pi_j\rightarrow \pi_k and \pi_{j'}\rightarrow \pi_k. Note that J\cap J'=\emptyset. Indeed, consider j'\in J', and j\neq j' in J such that \pi_j\rightarrow \pi_k and \pi_{j'}\rightarrow \pi_k. It follows from (2), (3) and (4) that j'\!=\!j\!-\!1 or j'\!=\!j\!+\!1. Since j\in J, m^1_{j} and m^2_{j} have the same parity as the big difference labels on T_5,\ldots,T_{2\theta}, which means that m^1_{j'} and m^2_{j'} have the opposite parity. Hence, there is no i with \pi_i\rightarrow \pi_{j'}, which proves that j'\notin J.

By flipping all \pi_{\ell} with \ell\in J\cup J', we get \pi_i\nrightarrow \pi_j for all 2\leq j< i\leq \theta with i or j in J\cup J'. Indeed, it follows from (1) that we cannot have \pi_i\rightarrow \pi_j with both i and j in J\cup J', since this would imply the existence of k,k' with 2\leq k < k'\leq \theta and \pi_{k'}\rightarrow \pi_i\rightarrow \pi_j\rightarrow \pi_k. Hence, it follows from (6) and (7) that \pi_i\nrightarrow \pi_j for i or j in J, 2\leq j< i \leq \theta. Moreover, as observed above, j'\in J' implies that m^1_{j'} and m^2_{j'} do not have the same parity as the big difference values on T_5,\ldots,T_{2\theta}. Hence, it follows from (6) that \pi_i\nrightarrow \pi_j for i or j in J', 2\leq j< i\leq \theta.

So, after the flipping of all \pi_{\ell} with \ell\in J\cup J', the remaining conflicts \pi_i\rightarrow \pi_j with 2\leq j < i\leq \theta are such that \{i,j\}\cap (J\cup J')=\emptyset . Consider any such conflict. If there is i'\neq i such that \pi_{i'}\rightarrow \pi_j, then we know from (4) that i'=i-1 or i+1. Without loss of generality, we may assume i'=i+1 (else we permute the roles of i and i'). Since none of j,i,i' belongs to J\cup J', there is no k such that \pi_k\rightarrow \pi_i, \pi_k\rightarrow \pi_{i'} or \pi_j\rightarrow \pi_k. Also, it follows from (4) that there is no k\neq i,i' such that \pi_k\rightarrow \pi_{j}

  • if i\leq 2\theta/3, we flip \pi_j. We then have \min\{|b^1_i|,|b^2_i|\}\geq 6\theta+3t-4(2\theta/3)-1=10\theta/3+3t-1. It follows that j\leq 2\theta/9 else \max\{|m^1_j|,|m^2_j|\}\leq 4\theta+3t-3(2\theta)/9-2=10\theta/3+3t-2. Hence \min\{|b^1_j|,|b^2_j|\}\geq 6\theta+3t-4(2\theta/9)-1=46\theta/9+3t-1>4\theta+3t-2. Since the medium magnitudes are at most equal to 4\theta+3t-2, we cannot have \pi_j\rightarrow \pi_k after the flip of \pi_j. Also, it follows from (7) that, after the flip of \pi_j, we have \pi_k\nrightarrow \pi_{j} for j< k\leq \theta. Hence, after the flip of \pi_j, the difference labels on its two triangles are different from those on the other triangles T_k, k\geq 5.
  • If i> 2\theta/3, we flip \pi_i and \pi_{i'} (if any). In this case, we have \max\{|m^1_{i'}|,|m^2_{i'}|\}< \max\{|m^1_i|,|m^2_i|\} \leq 4\theta+3t-3(2\theta/3)=2\theta+3t. Since all big magnitudes on T_1,\ldots,T_{2\theta} are strictly larger than 2\theta+3t, we cannot have \pi_k\rightarrow \pi_i after the flip of \pi_i and \pi_{i'}. Also, it follows from (6) that after the flip of \pi_i and \pi_{i'}, we have \pi_i\nrightarrow \pi_{k} and \pi_{i'}\nrightarrow \pi_{k} for 2\leq k< i. Hence, after the flip of \pi_i and \pi_{i'}, the difference labels on their triangles are different from those on the other triangles T_k, k\geq 5.

After all these flips, there is no \pi_i\rightarrow \pi_j with 2\leq j< i\leq \theta. We consider now triangles T_1,T_2,T_3,T_4 involved in \pi_0 and \pi_1. If there is j\geq 2 such that \pi_j\rightarrow \pi_1 then we know from (5) that \pi_j\nrightarrow \pi_k for all 2\leq k< j. Hence, j\notin J\cup J'. If, before the flips, there was i such that \pi_i\rightarrow \pi_j, then i> 2\theta/3. Indeed, we have seen above that if i\leq 2\theta/3, then \min\{|b^1_j|,|b^2_j|\}>4\theta+3t-2, which means that \pi_j\nrightarrow \pi_1. So, \pi_j was not flipped, and by flipping \pi_1, we get \pi_j\nrightarrow \pi_1 for all 2\leq j\leq \theta.

Since the parity of m^0_1 and m^0_2 is the opposite of the parity of b^1_i and b^2_i for all i\geq 2, we have \pi_j\nrightarrow \pi_0 for all 2\leq j\leq \theta. Hence, the only possible remaining conflict is between \pi_0 and \pi_1. This can only occur if b^0_1=b^1_1 and \pi_1 was flipped. In such a case, we flip \pi_0 to remove this last conflict.

Case B : n=2\theta+t, \theta=3t+1 We treat this case as the previous one. More precisely, the vertex labels f(v_i) on T_1,\ldots,T_{2\theta} are given in Table 4. Given a gdl f' for t\overrightarrow{\bf C_3} with at most one arc of magnitude 3t-2, and all other arcs of magnitude strictly smaller than 3t-2, we set f(v_i)=f'(v_i)+3\theta for i=6\theta+1,\ldots,6\theta+3t. Again, one can easily check that f is a bijection between \{v_1,\ldots,v_{6\theta+3t}\} and \{1, \ldots,6\theta+3t=3n\}.
Table 4. The labeling of T_1,\ldots,T_{2\theta} for case B.
Triangle T_i f(v_{3i-2}) f(v_{3i-1}) f(v_{3i})
T_1 1 2\theta+1 6\theta+3t-3
T_2 2 6\theta+3t 4\theta+3t
T_3 3 6\theta+3t-1 2\theta+2
T_4 4 4\theta+3t-1 6\theta+3t-2
\vdots \vdots \vdots \vdots
T_{2k-1} 2k-1 2\theta+k 6\theta+3t-2k+2
T_{2k} 2k 6\theta+3t-2k+1 4\theta+3t-k+1
\vdots \vdots \vdots \vdots
T_{2\theta-1} 2\theta-1 3\theta+3t+1 4\theta+3t+1
T_{2\theta} 2\theta 4\theta+3t+2 3\theta
The small, medium, and big difference labels for triangles T_1,\ldots,T_{2\theta} are given in Table 5. Again, the triangles are grouped in pairs, using two dummy triangles D_1 and D_2 which are paired with T_5 and T_{2\theta-2}, respectively. Notice that for every uv on a T_i with i\leq 2\theta and every u'v' on a T_j with j>2\theta, we have f(v)-f(u)\neq f(v')-f(u') since the smallest possible magnitude for uv is \theta=3t+1, while the largest possible magnitude for u'v' is 3t-2. Hence, in this case, we do not have to flip triangles T_{2\theta+1},\ldots,T_{2\theta+t}. Note also that the largest magnitude is 6\theta+3t-2= 3n-2, and there is exactly one arc with this magnitude.
Table 5. The difference labels of the arcs of T_1,\ldots,T_{2\theta},D_1,D_2 for case B.
Pair Triangle Small-dl Medium-dl Big-dl
\pi_0=(T_1,T_2) T_1 2\theta 4\theta+3t-4 -(6\theta+3t-4)
T_2
-2\theta -(4\theta+3t-2) 6\theta+3t-2
\pi_1=(T_3,T_4) T_3 -(2\theta-1) -(4\theta+3t-3) 6\theta+3t-4
T_4 2\theta-1 4\theta+3t-5 -(6\theta+3t-6)
\pi_2=(D_1,T_5) D_1 -(2\theta-2) -(4\theta+3t-5) 6\theta+3t-7
T_5 2\theta-2 4\theta+3t-7 -(6\theta+3t-9)
\vdots \vdots \vdots \vdots \vdots
\pi_k=(T_{2k},T_{2k+1}) T_{2k} -(2\theta-k) -(4\theta+3t-3k+1) 6\theta+3t-4k+1
k=3,\ldots,\theta-2 T_{2k+1} 2\theta-k 4\theta+3t-3k-1 -(6\theta+3t-4k-1)
\vdots \vdots \vdots \vdots \vdots
\pi_{\theta-1}=(T_{2\theta-2},D_{2}) T_{2\theta-1} -(\theta+1) -(\theta+3t+4) 2\theta+3t+5
D_{2} \theta+1 \theta+3t+2 -(2\theta+3t+3)
\pi_{\theta}=(T_{2\theta-1},T_{2\theta}) T_{2\theta-1} \theta \theta+3t+2 -(2\theta+3t+2)
T_{2\theta} -\theta -(\theta+3t+2) 2\theta+3t+2
Since \theta=3t+1, we have \theta+3t+2=2\theta+1, which means that no medium-dl can be equal to a small-dl. The small, medium and big difference labels on T_1,\ldots,T_{2\theta-2} are exactly the same as those of Table 3. Using the same arguments, as in the previous case, we can avoid conflicts involving medium and big difference labels of \pi_0,\ldots,\pi_{\theta-1}. Consider now \pi_{\theta}:
  • The medium difference values of \pi_{\theta} can only be conflicting with the medium-dl of D_2, but we don't care about such a conflict since D_2 is a dummy triangle;
  • The big difference values of \pi_{\theta} can only be conflicting with the medium-dl of a T_k. For this to happen, we should have 2\theta+3t+2 equal to 4\theta+3t-3k+1 or 4\theta+3t-3k-1, or equivalently k equal to \frac{2\theta-1}{3}=\frac{6t+1}{3} or \frac{2\theta-3}{3}=\frac{6t-1}{3}, which is impossible since k is an integer.
Case C : n=2\theta+t-1, \theta\in\{3t-1,3t\}
Again, consider the vertex labels f(v_i) on T_1,\ldots,T_{2\theta-1} shown in Table \ref{num3}. Given a gdl f' for t\overrightarrow{\bf C_3} with at most one arc of magnitude 3t-2, and all other arcs of magnitude strictly smaller than 3t-2, we set f(v_i)=f'(v_i)+3\theta-1 for i=6\theta-2,\ldots,6\theta+3t-3. One can easily check f is a bijection between \{v_1,\ldots,v_{6\theta+3t-3}\} and \{1, \ldots,6\theta+3t-3=3n\}. The small, medium, and big difference labels for triangles T_1,\ldots,T_{2\theta} are given in Table \ref{dl3}.
Table 6. The labeling of T_1,\ldots,T_{2\theta-1} for case C.
Triangle T_i f(v_{3i-2}) f(v_{3i-1}) f(v_{3i})
T_1 1 2\theta 6\theta+3t-6
T_2 2 6\theta+3t-3 4\theta+3t-2
T_3 3 6\theta+3t-4 2\theta+1
T_4 4 4\theta+3t-3 6\theta+3t-5
T_5 5 2\theta+2 6\theta+3t-7
\vdots \vdots \vdots \vdots
T_{2k} 2k 6\theta+3t-2k-2 4\theta+3t-k-1
T_{2k+1} 2k+1 2\theta+k 6\theta+3t-2k-3
k=3,\ldots,\theta-3
\vdots \vdots \vdots \vdots
Table 7. The difference labels of the arcs of T_1,\ldots,T_{2\theta-1},D_1 for case C.
Pair Triangle Small-dl Medium-dl Big-dl
\pi_0=(T_1,T_2) T_1 2\theta-1 4\theta+3t-6 -(6\theta+3t-7)
T_2 -(2\theta-1) -(4\theta+3t-4) 6\theta+3t-5
\pi_1=(T_3,T_4) T_3 -(2\theta-2) -(4\theta+3t-5) 6\theta+3t-7
T_4 2\theta-2 4\theta+3t-7 -(6\theta+3t-9)
\pi_2=(D_1,T_5) D_1 -(2\theta-3) -(4\theta+3t-7) 6\theta+3t-10
T_5 2\theta-3 4\theta+3t-9 -(6\theta+3t-12)
\vdots \vdots \vdots \vdots \vdots
\pi_k=(T_{2k},T_{2k+1}) T_{2k} -(2\theta-k-1) -(4\theta+3t-3k-1) 6\theta+3t-4k-2
k=3,\ldots,\theta-1 T_{2k+1} 2\theta-k-1 4\theta+3t-3k-3 -(6\theta+3t-4k-4)
\vdots \vdots \vdots \vdots \vdots

Again, the triangles are grouped in pairs, using one dummy triangle D_1 which is paired with T_5. Notice that for every uv on a T_i with i\leq 2\theta-1 and every u'v' on a T_j with j>2\theta-1, we have f(v)-f(u)\neq f(v')-f(u') since the smallest possible magnitude for uv is \theta\geq 3t-1, while the largest possible magnitude for u'v' is 3t-2. Hence, also in this case, we do not have to flip T_{2\theta+1},\ldots,T_{2\theta+t}. Note also that the largest magnitude is 6\theta+3t-5=3n-2, and there is exactly one arc with this magnitude.

Since \theta< 3t+1, we have \theta+3t>2\theta-1, which means that no medium-dl can be equal to a small-dl. Using the same arguments, as in the previous cases, we can avoid conflicts involving \pi_2,\ldots,\pi_{\theta-1}.

If there is j\geq 2 such that \pi_j\rightarrow \pi_0, then assume there is i>j such that \pi_i\rightarrow \pi_j. If i\leq 2\theta/3, then \min\{|b^1_i|,|b^2_i|\}\geq 6\theta+3t-4(2\theta/3)-4=10\theta/3+3t-4. It follows that j\leq (2\theta+3)/9 else \max\{|m^1_j|,|m^2_j|\}\leq 4\theta+3t-3(2\theta+3)/9-4=10\theta/3+3t-5. Hence \min\{|b^1_j|,|b^2_j|\}\geq 6\theta+3t-4(2\theta+3)/9-4=46\theta/9+3t-48/9>4\theta+3t-4, which contradicts \pi_j\rightarrow \pi_0. Hence, we necessarily have i>2\theta/3, and since j cannot belong to J\cup J', we conclude that j was not flipped. Hence, by flipping \pi_0, we get \pi_j\nrightarrow \pi_0 for all j\geq 2.

Since the parity of m^1_1 and m^2_1 is the opposite of the parity of b^1_i and b^2_i for all i\geq 2, we have \pi_j\nrightarrow \pi_1 for all j\geq 2. Hence, the only possible remaining conflict is between \pi_0 and \pi_1. This can only occur if b^1_0=b^1_1 and \pi_1 was flipped. In such a case, we flip \pi_1 to remove this last conflict.

Case D : n=2\theta+t-1, \theta=3t+1 Consider the vertex labels f(v_i) on T_1,\ldots,T_{2\theta-1} shown in Table 8. Given a gdl f' for t\overrightarrow{\bf C_3} with at most one arc of magnitude 3t-2, and all other arcs of magnitude strictly smaller than 3t-2, we set f(v_i)=f'(v_i)+3\theta-1 for i=6\theta-2,\ldots,6\theta+3t-3. One can easily check f is a bijection between \{v_1,\ldots,v_{6\theta+3t-3}\} and \{1, \ldots,6\theta+3t-3=3n\}.

The small, medium, and big difference labels for triangles T_1,\ldots,T_{2\theta} are given in Table \ref{dl4}. Again, the triangles are grouped in pairs, using one dummy triangle D_1 which is paired with T_5. Notice that for every uv on a T_i with i\leq 2\theta-1 and every u'v' on a T_j with j>2\theta-1, we have f(v)-f(u)\neq f(v')-f(u') since the smallest possible magnitude for uv is \theta-2=3t-1, while the largest possible magnitude for u'v' is 3t-2. Hence, also in this case, we do not have to flip T_{2\theta+1},\ldots,T_{2\theta+t}. Note also that the largest magnitude is 6\theta+3t-5=3n-2, and there is only one arc with this magnitude.

Since \theta=3t+1, we have \theta+3t+1=2\theta, which means that no medium-dl can be equal to a small-dl. The small, medium and big difference labels on T_1,\ldots,T_{2\theta-5} are exactly the same as those of Table \ref{dl3}. Using the same arguments, as in the previous case, we can avoid conflicts involving \pi_0,\ldots,\pi_{\theta-3}.

Table 8. The labeling of T_1,\ldots,T_{2\theta-1} for case D.
Triangle T_i f(v_{3i-2}) f(v_{3i-1}) f(v_{3i})
T_1 1 2\theta 6\theta+3t-6
T_2 2 6\theta+3t-3 4\theta+3t-2
T_3 3 6\theta+3t-4 2\theta+1
T_4 4 4\theta+3t-3 6\theta+3t-5
T_5 5 2\theta+2 6\theta+3t-7
\vdots \vdots \vdots \vdots
T_{2k} 2k 6\theta+3t-2k-2 4\theta+3t-k-1
T_{2k+1} 2k+1 2\theta+k 6\theta+3t-2k-3
k=3,\ldots,\theta-3
\vdots \vdots \vdots \vdots
T_{2\theta-4} 2\theta-4 4\theta+3t-1 3\theta+3t+1
T_{2\theta-3} 2\theta-3 4\theta+3t+2 3\theta-2
T_{2\theta-2} 2\theta-2 3\theta+3t 4\theta+3t+1
T_{2\theta-1} 2\theta-1 3\theta-1 4\theta+3t

Table 9. The difference labels of the arcs of T_1,\ldots,T_{2\theta-1},D_1 for case D.
Triangle T_i f(v_{3i-2}) f(v_{3i-1}) f(v_{3i})
T_1 1 2\theta 6\theta+3t-6
T_2 2 6\theta+3t-3 4\theta+3t-2
T_3 3 6\theta+3t-4 2\theta+1
T_4 4 4\theta+3t-3 6\theta+3t-5
T_5 5 2\theta+2 6\theta+3t-7
\vdots \vdots \vdots \vdots
T_{2k} 2k 6\theta+3t-2k-2 4\theta+3t-k-1
T_{2k+1} 2k+1 2\theta+k 6\theta+3t-2k-3
k=3,\ldots,\theta-3
\vdots \vdots \vdots \vdots
T_{2\theta-4} 2\theta-4 4\theta+3t-1 3\theta+3t+1
T_{2\theta-3} 2\theta-3 4\theta+3t+2 3\theta-2
T_{2\theta-2} 2\theta-2 3\theta+3t 4\theta+3t+1
T_{2\theta-1} 2\theta-1 3\theta-1 4\theta+3t
Consider now \pi_{\theta-2} and \pi_{\theta-1}. The medium magnitudes |m^1_{\theta-2}|,|m^2_{\theta-2}|,|m^1_{\theta-1}| and |m^2_{\theta-1}| do not appear on any other triangle. Also, the medium magnitudes on a \pi_k with 2\leq k\leq \theta-3 are equal to 4\theta+3t-3k-1=15t-3k+3 or 4\theta+3t-3k-3=15t-3k+1, which mean that they are all equal to 0, or 1\mod 3. Hence, the big magnitudes |b^2_{\theta-2}|=|b^2_{\theta-1}|=2\theta+3t+3=9t+5 do not appear on any other triangle as medium magnitude. Therefore, these two big magnitudes will not be conflicting if we either flip both \pi_{\theta-1} and \pi_{\theta-2}, or none of them. The only remaining possible conflicts involve a medium-dl on a T_i (i< \theta-2) and b^1_{\theta-2} or b^1_{\theta-1} Assume there is a triangle T_i with magnitude 2\theta+3t+1=|b^1_{\theta-1}|. This means that 2\theta+3t+1\leq 4\theta+3t-3i-1, which is equivalent to i\leq (2\theta-2)/3. Hence, \pi_i was not flipped. Also, if there is a triangle T_j with magnitude 2\theta+3t+5=b^1_{\theta-2}, then j< i\leq (2\theta-2)/3, which means that \pi_j was not flipped. Now,
  • If there is a triangle T_i with medium-dl -(2\theta+3t+1), then m^1_{i}=b^1_{\theta-1}, and m^2_{i-2}=-b^1_{\theta-1}+4=2\theta+3t+5=b^1_{\theta-2}, and we can avoid both conflicts by flipping both \pi_{\theta-1} and \pi_{\theta-2};
  • If there is a triangle T_j with medium-dl 2\theta+3t+5, then m^2_{j}=b^1_{\theta-2}, and m^1_{j+2}=-b^1_{\theta-2}+4=-(2\theta+3t+1)=b^1_{\theta-1}, and we can avoid both conflicts by flipping both \pi_{\theta-1} and \pi_{\theta-2}.
  • If there is no triangle with medium-dl -(2\theta+3t+1) or 2\theta+3t+5, there is no conflict.

We already know from Lemma \ref{C2k+1C4} that \overrightarrow{\bf C_4}+\overrightarrow{\bf C_3} has a gdl. We now show that this is also the case for \overrightarrow{\bf C_4}+n\overrightarrow{\bf C_3}, n\geq 2.

Lemma\label{C4C3} \overrightarrow{\bf C_4}+n\overrightarrow{\bf C_3} has a gdl for every n\ge 1.

Proof. The graphs in Figures 9, 10, 11, 12, 13, 14 and 15 show the existence of the desired gdl for 2\leq n \leq 8.

Figure 9. 2\overrightarrow{\bf C_3}+\overrightarrow{\bf C_4}.

Figure 10. 3\overrightarrow{\bf C_3}+\overrightarrow{\bf C_4}.

Figure 11. 4\overrightarrow{\bf C_3}+\overrightarrow{\bf C_4}.

Figure 12. 5\overrightarrow{\bf C_3}+\overrightarrow{\bf C_4}.

Figure 13. 6\overrightarrow{\bf C_3}+\overrightarrow{\bf C_4}.

Figure 14. 7\overrightarrow{\bf C_3}+\overrightarrow{\bf C_4}.

Figure 15. 8\overrightarrow{\bf C_3}+\overrightarrow{\bf C_4}

For n\ge 9, we know from Lemma 7 that there is a gdl for (n+1)\overrightarrow{\bf C_3}, which can be obtained by performing a set F of flips, starting from the labelling f defined in Tables 2, 4, 6, and 8 for cases A, B, C and D, respectively. We distinguish two cases.
  • For cases A and B, we consider the graph G obtained from (n+1)\overrightarrow{\bf C_3} by inserting a new vertex v_0 between v_5 and v_6. More precisely, G is obtained by replacing T_2 in (n+1)\overrightarrow{\bf C_3} by a \overrightarrow{\bf C_4} with vertex set \{v_0,v_4,v_5,v_6\} and arc set \{v_4v_5,v_5v_0,v_0v_6,v_6v_4\}. We then define f' by setting f'(v_0)=1 and f'(v_i)=f(v_i)+1 for i=1,\ldots,3(n+1). Clearly, f' is bijection between \{v_0,\ldots,v_{3(n+1)}\} and \{1,\ldots,3n+4\}. In order to prove that by performing exactly the same set F of flips, we get a gdl for G, it is sufficient to show that the difference labels on v_5v_0 and v_0v_6 cannot appear on other arcs of G.
    • \vert f'(v_0)-f'(v_5)\vert=\vert 1-(6\theta+3t+1)\vert =6\theta+3t, which means that v_5v_0 has a magnitude larger than that of any other arc in G.
    • f'(v_6)-f'(v_0)=(4\theta+3t+1)-1=4\theta+3t. Since this value is strictly larger than any other medium magnitude in G, the difference label on v_0v_6 can only be conflicting with a big-dl on a T_i with i\geq 5. But this does not occur since these big difference labels have the opposite parity of 4\theta+3t.
  • For cases C and D, we consider the graph G obtained from (n+1)\overrightarrow{\bf C_3} by inserting a new vertex v_0 between v_9 and v_7. More precisely, G is obtained by replacing T_3 in (n+1)\overrightarrow{\bf C_3} by a \overrightarrow{\bf C_4} with vertex set \{v_0,v_7,v_8,v_9\} and arc set \{v_7v_8,v_8v_9,v_9v_0,v_0v_7\}. We then define f' by setting f'(v_0)=3n+4=6\theta+3t-2 and f'(v_i)=f(v_i) for i=1,\ldots,3(n+1). Clearly, f' is bijection between \{v_0,\ldots,v_{3(n+1)}\} and \{1,\ldots,3n+4\}. In order to prove that by performing exactly the same set F of flips, we get a gdl for G, it is sufficient to show that the difference labels on v_0v_7 and v_9v_0 do not appear on other arcs of G.
    • f'(v_7)-f'(v_0)=3-(6\theta+3t-2) =-(6\theta+3t-5). The same difference label appears on T_2 but with an opposite sign. These two arcs could be conflicting if exaclty one of \pi_{0} and \pi_{1} is flipped, but this does not occur since T_1 and T_3 have big difference labels of the same magnitude, but with opposite signs.
    • f'(v_0)-f'(v_9)=(6\theta+3t-2)-(2\theta+1)=4\theta+3t-3. Since this value is strictly larger than any other medium magnitude in G, the difference label on v_9v_0 can only be conflicting with a big-dl on a T_i with i\geq 5. But this does not occur since these big difference labels have the opposite parity of 4\theta+3t-3.

All together, the results shown in the eight lemmas of this section can be summarized as follows.

Theorem 1. If G is the disjoint union of circuits, among which at most one has an odd length, or all circuits of odd length have 3 vertices, then G has a gdl, unless G=\overrightarrow{\bf C_{3}} or G=\overrightarrow{\bf C_{2}}+\overrightarrow{\bf C_{3}}.

3. Conclusion

As mentioned in the introduction, it is an open question to determine the values of n for which n\overrightarrow{\bf C_{3}} has a graceful labeling, i.e., an injection f:V\rightarrow\{0,1,\ldots,q\} such that, when each arc xy is assigned the label (f(y)-f(x))\ (mod\ q+1), the resulting arc labels are distinct. Considering graceful difference labelings, we could show that n\overrightarrow{\bf C_{3}} has a gdl if and only if n\geq 2. We have also proved additional cases that support the following conjecture.

Conjecture 1. If G is the disjoint union of circuits, then G has a gdl, unless G=\overrightarrow{\bf C_{3}} or G=\overrightarrow{\bf C_{2}}+\overrightarrow{\bf C_{3}}.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.

References

  1. Gallian, J. A. (2009). A dynamic survey of graph labeling. The electronic journal of combinatorics, 16(6), 1-219.[Google Scholor]
  2. Rosa, A. (1966, July). On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Symposium, Rome (pp. 349-355).[Google Scholor]
  3. Golomb, S. W. (1972). How to number a graph. In Graph theory and computing (pp. 23-37). Academic press.[Google Scholor]
  4. Feng, W., & Xu, C. (2011). A survey of the gracefulness of digraphs. International Journal of Pure and Applied Mathematics, 69(3), 245.[Google Scholor]
  5. West, D. B. (1996). Introduction to graph theory (Vol. 2). Upper Saddle River, NJ: Prentice hall.[Google Scholor]