Open Journal of Discrete Applied Mathematics
ISSN: 2617-9687 (Online) 2617-9679 (Print)
DOI: 10.30538/psrp-odam2019.0021
On graceful difference labelings of disjoint unions of circuits
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
Keywords:
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 n→C3, 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 u′v′ 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 Vi∩Vj=∅, their disjoint union, denoted Gi+Gj, is the graph with vertex set Vi∪Vj and arc set Ai∪Aj. By pG we denote the disjoint union of p copies of G. For k≥2 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: 1≤i<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.
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 k≥4, 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 k≥6, 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 n≥2 circuits of length 3 has a gdl, and this is also the case if a →C4 is added to n→C3. Hence, if G is the union of disjoint circuits with no odd circuit of length k≥5, 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 k≥5, 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 k≥4 has a gdl. Moreover, if k≥5, 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 k≥4. We distinguish four cases, according to the value of kmod4:
- If k=4p,p≥1, we consider the following vertex labels:
- f(v2i+1)=i+1,0≤i≤2p−2;
- f(v2i)=4p+1−i,1≤i≤2p−2;
- f(v4p−2)=2p+1, f(v4p−1)=2p+2, f(v4p)=2p.
- f(vi+1)−f(vi)=(−1)i+1(4p−i),1≤i≤4p−4;
- f(v4p−2)−f(v4p−3)=2, f(v4p−1)−f(v4p−2)=1, f(v4p)−f(v4p−1)=−2, f(v1)−f(v4p)=−2p+1.
- f(v4p−2)−f(v4p−3)=2 and f(v4p)−f(v4p−1)=−2;
- for p≥3, f(v2p+2)−f(v2p+1)=2p−1 and f(v1)−f(v4p)=−(2p−1);
- for p=1, f(v4p−1)−f(v4p−2)=1 and f(v1)−f(v4p)=−1.
- If k=4p+1,p≥1, we consider the following vertex labels:
- f(v2i+1)=i+1,0≤i≤2p;
- f(v2i)=4p+2−i,1≤i≤2p.
- f(vi+1)−f(vi)=(−1)i+1(4p+1−i),1≤i≤4p;
- f(v1)−f(v4p+1)=−2p.
- If k=4p+2,p≥0, we consider the following vertex labels:
- f(v2i+1)=i+1,0≤i≤2p;
- f(v2i)=4p+3−i,1≤i≤2p+1.
- f(vi+1)−f(vi)=(−1)i+1(4p+2−i),1≤i≤4p+1;
- f(v1)−f(v4p+2)=−2p−1.
- If k=4p+3,p≥1, we consider the following vertex labels:
- f(v2i+1)=i+1,0≤i≤2p−1;
- f(v2i)=4p+4−i,1≤i≤2p;
- f(v4p+1)=2p+2, f(v4p+2)=2p+1, f(v4p+3)=2p+3.
- f(vi+1)−f(vi)=(−1)i+1(4p+3−i),1≤i≤4p−1;
- 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).
- f(v4p−2)−f(v4p−3)=2 and f(v4p)−f(v4p−1)=−2;
- f(v2p+2)−f(v2p+1)=2p+2 and f(v1)−f(v4p+3)=−(2p+2).
Lemma 2. If a graph G has a gdl, then G+2→C4 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 v∈V 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+2→C4.
Note that in the proof of Lemma 2, G can be the empty graph G with no vertex and no arc. Hence 2→C4 has a gdl.Lemma 3. If a graph G has a gdl, then G+→C2k also has a gdl for k≥1,k≠2.
Proof. Suppose G=(V,A) has a gdl f, and let {v1,…,v2k} be the vertex set and {v1v2,…,v2k−1v2k,v2kv1} be the arc set of →C2k. We consider two case.
- If k is odd, then define f′(v)=f(v)+k for all v∈V, as well as f′(v2i−1)=k−i+1 and f′(v2i)=|V|+k+i for 1≤i≤k. 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 v∈V, and define the vertex labels on →C2k as follows:
- f′(v2i−1)=k−i+1 for 1≤i≤k;
- f′(v2i)=|V|+k+i for 1≤i≤k−3;
- f′(v2k−4)=|V|+2k,f′(v2k−2)=|V|+2k−2,f′(v2k)=|V|+2k−1.
- f′(vk)−f′(vk−1)=|V|+k−1 and f′(v1)−f′(v2k)=−(|V|+k−1);
- f′(v2k−4)−f′(v2k−5)=|V|+2k−3 and f′(v2k−1)−f′(v2k−2)=−(|V|+2k−3).
Lemma 4. 2→C2+→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 2→C2+→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 k≥1.
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,vn−2,vn−1,vn} is the vertex set of the →C4 in G, while {v2,v3,…,vn−3} is the vertex set of the →C2k+1. It is sufficient to prove that the difference labels on v1vn−2 and vn−3v2 do not appear on any other arc of G.
- f(vn−2)−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(vn−3)=(4p+3)−(2p+4)=2p−1=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+1≥2 (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)−(2p−1)=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 k≥5.
Proof. Let {v1,…,vk+3} be the vertex set and {v1v2,…,vk−1vk, 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 G≠→C3 and G≠→C2+→C3.
We now consider the disjoint union of n circuits of length 3, and show that these graphs have a gdl for all n≥2.Lemma 7. For every n≥2, the graph n→C3 has a gdl with at most one arc of magnitude 3n−2, and all other arcs of magnitude strictly smaller than 3n−2.
Proof. The graphs in Figures 1, 2, 3, 4, 5, 6, 7 and 8 show the existence of the desired gdl for 2≤n≤9.
Figure 1. 2→C3.
Figure 2. 3→C3
Figure 3. 4→C3.
Figure 4. 5→C3.
Figure 5. 6→C3.
Figure 6. 7→C3.
Figure 7. 8→C3.
Figure 8. 9→C3.
We now prove the result by induction on n. So, consider the graph n→C3 with n≥10, and assume the result is true for less than n directed triangles. Let t and r be two integers such that −4≤r≤2 and n=7t+r.
We thus have t≥2. We will show how to construct a gdl for n→C3 given a gdl for t→C3. We thus have to add n−t directed triangles to t→C3. For this purpose, define θ=⌈n−t2⌉=3t+⌈r2⌉.
It follows that n−t=2θ if r is even, and n−t=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.
n−t | r | θ | Case |
---|---|---|---|
2θ | -4 | 3t−2 | A |
-2 | 3t−1 | ||
0 | 3t | ||
2 | 3t+1 | B | |
2θ−1 | -3 | 3t−1 | C |
-1 | 3t | ||
1 | 3t+1 | D |
Table 2. The labeling of T1,…,T2θ for case A.
Triangle Ti | f(v3i−2) | f(v3i−1) | f(v3i) |
---|---|---|---|
T1 | 1 | 2θ | 6θ+3t−6 |
T2 | 2 | 6θ+3t−3 | 4θ+3t−2 |
T3 | 3 | 6θ+3t−4 | 2θ+1 |
T4 | 4 | 4θ+3t−1 | 6θ+3t−2 |
⋮ | ⋮ | ⋮ | ⋮ |
T2k−1 | 2k−1 | 2θ+k | 6θ+3t−2k+2 |
T2k | 2k | 6θ+3t−2k+1 | 4θ+3t−k+1 |
k=3,…,θ−3 | |||
⋮ | ⋮ | ⋮ | ⋮ |
Also, let f′ be a gdl for t→C3 with at most one arc of magnitude 3t−2, and all other arcs of magnitude strictly smaller than 3t−2. 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(v3i−1)−f(v3i−2)|, |f(v3i)−f(v3i−1)|, and |f(v3i−2)−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θ+3t−4 | −(6θ+3t−4) |
T2 |
−2θ | −(4θ+3t−2) | 6θ+3t−2 | |
π1=(T3,T4) | T3 | −(2θ−1) | −(4θ+3t−3) | 6θ+3t−4 |
T4 | 2θ−1 | 4θ+3t−5 | −(6θ+3t−6) | |
π2=(D1,T5) | D1 | −(2θ−2) | −(4θ+3t−5) | 6θ+3t−7 |
T5 | 2θ−2 | 4θ+3t−7 | −(6θ+3t−9) | |
⋮ | ⋮ | ⋮ | ⋮ | ⋮ |
πk=(T2k,T2k+1) | T2k | −(2θ−k) | −(4θ+3t−3k+1) | 6θ+3t−4k+1 |
k=3,…,θ−1 | T2k+1 | θ−k | 4θ+3t−3k−1 | −(6θ+3t−4k−1) |
⋮ | ⋮ | ⋮ | ⋮ | ⋮ |
πθ=(T2θ,D2) | T2θ | −θ | −(θ+3t+1) | 2θ+3t+1 |
D2 | θ | θ+3t−1 | −(2θ+3t−1) |
- s1i, m1i and b2i are negative integers, while s2i, m2i and b1i are positive integers;
- s2i=−s1i, m2i=−m1i−2, and b2i=−b1i+2;
- if i<θ, then s1i+1=s1i+1, m1i+1=m1i+3, and b1i+1=b1i−4.
- 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
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
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: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: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 |
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 |
- 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.
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 |
- 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.
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 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.
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
- Gallian, J. A. (2009). A dynamic survey of graph labeling. The electronic journal of combinatorics, 16(6), 1-219.[Google Scholor]
- 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]
- Golomb, S. W. (1972). How to number a graph. In Graph theory and computing (pp. 23-37). Academic press.[Google Scholor]
- Feng, W., & Xu, C. (2011). A survey of the gracefulness of digraphs. International Journal of Pure and Applied Mathematics, 69(3), 245.[Google Scholor]
- West, D. B. (1996). Introduction to graph theory (Vol. 2). Upper Saddle River, NJ: Prentice hall.[Google Scholor]