ars mathematica contemporanea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 12 (2017) 235-245 Distance labelings: a generalization of Langford sequences S. C. Lopez * Departament de Matematiques Universität Politecnica de Catalunya C/Esteve Terrades 5, 08860 Castelldefels, Spain F. A. Muntaner-Batle Graph Theory and Applications Research Group School of Electrical Engineering and Computer Science Faculty of Engineering and Built Environment The University of Newcastle NSW 2308 Australia Received 16 July 2015, accepted 31 March 2016, published online 5 December 2016 A Langford sequence of order m and defect d can be identified with a labeling of the vertices of a path of order 2m in which each label from d up to d + m - 1 appears twice and in which the vertices that have been labeled with k are at distance k. In this paper, we introduce two generalizations of this labeling that are related to distances. The basic idea is to assign nonnegative integers to vertices in such a way that if n vertices (n > 1) have been labeled with k then they are mutually at distance k. We study these labelings for some well known families of graphs. We also study the existence of these labelings in general. Finally, given a sequence or a set of nonnegative integers, we study the existence of graphs that can be labeled according to this sequence or set. Keywords: Langford sequence, distance l-labeling, distance J-labeling, S-sequence, S-set. Math. Subj. Class.: 11B99, 05C78 * Supported by the Spanish Research Council under project MTM2014-60127-P and symbolically by the Catalan Research Council under grant 2014SGR1147. E-mail addresses: susana.clara.lopez@upc.edu (S. C. Lopez), famb1es@yahoo.es (F. A. Muntaner-Batle) Abstract ©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/ 235 Ars Math. Contemp. 12 (2017) 383-413 1 Introduction For the graph terminology not introduced in this paper we refer the reader to [14, 15]. For m < n, we denote the set {m, m + 1,..., n} by [m, n]. A Skolem sequence [8, 12] of order m is a sequence of 2m numbers (si, s2,..., «2m) such that (i) for every k g [1, m] there exist exactly two subscripts i, j g [1,2m] with sj = sj = k, (ii) the subscripts i and j satisfy the condition |i - j | = k. The sequence (4,2, 3, 2,4,3,1,1) is an example of a Skolem sequence of order 4. It is well known that Skolem sequences of order m exist if and only if m = 0 or 1 (mod 4). Skolem introduced in [13] what is now called a hooked Skolem sequence of order m, where there exists a zero at the second to last position of the sequence containing 2m + 1 elements. Later on, in 1981, Abrham and Kotzig [1] introduced the concept of extended Skolem sequence, where the zero is allowed to appear in any position of the sequence. An extended Skolem sequence of order m exists for every m. The following construction was given in [1]: (Pm,Pm-2,. .., 2, 0, 2, .. . ,pm -2,pm, qm, -2,. .., 3,1, 1, 3,.. ., qm-2, qm), (1.1) where pm and qm are the largest even and odd numbers not exceeding m, respectively. Notice that from every Skolem sequence we can obtain two trivial extended Skolem sequences just by adding a zero either in the first or in the last position. Let d be a positive integer. A Langford sequence of order m and defect d [11] is a sequence (11,l2,..., l2m) of 2m numbers such that (i) for every k g [d, d + m - 1] there exist exactly two subscripts i, j g [1, 2m] with lj = j = k, (ii) the subscripts i and j satisfy the condition |i - j | = k. Langford sequences, for d = 2, were introduced in [4] and they are referred to as perfect Langford sequences. Notice that, a Langford sequence of order m and defect d =1 is a Skolem sequence of order m. Bermond, Brower and Germa on one side [2], and Simpson on the other side [11] characterized the existence of Langford sequences for every order m and defect d. Theorem 1.1. [2,11] A Langford sequence of order m and defect d exists if and only if the following conditions hold: (i) m > 2d - 1, and (ii) m = 0 or 1 (mod 4) if d is odd; m = 0 or 3 (mod 4) if d is even. For a complete survey on Skolem-type sequences we refer the reader to [3]. For different constructions and applications of Langford type sequences we also refer the reader to [5, 6, 7, 9, 10]. 1.1 Distance labelings Let L = (11,12,..., l2m) be a Langford sequence of order m and defect d. Consider a path P with V(P) = {v. : i =1, 2,..., 2m} and E(P) = {vivi+1 : i =1, 2, 2m - 1}. Then, we can identify L with a labeling f : V(P) ^ [d, d + m - 1] in such a way that, (i) for every k g [d, d + m - 1] there exist exactly two vertices vj, vj g [1,2m] with f K) = f (vj) = k, (ii) the distance d(v^ vj) = k. Motivated by this fact, we introduce two notions of distance labelings, one of them associated with a positive integer l and the other one associated with a set of positive integers J. Let G be a graph and let l be a nonnegative integer. Consider any function f : V(G) ^ [0, l]. We say that f is a distance labeling of length l (or distance l-labeling) of G if the following two conditions hold, (i) either f (V(G)) = [0, l] or f (V(G)) = [1,l] and (ii) S. C. Lopez and F. A. Muntaner-Batle: Distance labelings 237 if there exist two vertices vj, vj with f (vj) = f (vj) = k then d(vi,vj) = k. Clearly, a graph can have many different distance labelings. We denote by A(G), the labeling length of G, the minimum l for which a distance l-labeling of G exists. We say that a distance l-labeling of G is proper if for every k g [1, l] there exist at least two vertices vj, vj of G with f (vj) = f (vj) = k. We also say that a proper distance l-labeling of G is regular of degree r (for short r-regular) if for every k g [1, l] there exist exactly r vertices vj1, vj2, ..., vjr with f (vj1) = f (vj2) = ... = f (vjr) = k. Clearly, if a graph G admits a proper distance l-labeling then l < D(G), where D(G) is the diameter of G. Let G be a graph and let J be a set of nonnegative integers. Consider any function f : V(G) ^ J. We say that f is a distance J-labeling of G if the following two conditions hold, (i) f (V(G)) = J and (ii) for any pair of vertices vj, vj with f (vj) = f (vj) = k we have that d(vj, vj) = k. We say that a distance J-labeling is proper if for every k g J\ {0} there exist at least two vertices vj, vj with f (vj) = f (vj) = k. We also say that a proper distance J-labeling of G is regular of degree r (for short r-regular) if for every k g J \ {0} there exist exactly r vertices vj1, vj2, ..., vjr with f (vj1) = f (vj2) = ... = f (vjr) = k. Clearly, a distance l-labeling is a distance J-labeling in which either J = [0, l] or J = [1, l]. Thus, the notion of a J-labeling is more general than the notion of a l-labeling. In this paper, we provide the labeling length of some well known families of graphs. We also study the inverse problem, that is, for a given pair of positive integers l and r we ask for the existence of a graph of order lr with a regular l-labeling of degree r. Finally, we study a similar question when we deal with J-labelings. The organization of the paper is as follows. Section 2 is devoted to l-labelings; we start calculating the labeling length of complete graphs, paths, cycles and some others families. The inverse problem is studied in the second part of the section. Section 3 is devoted to the inverse problem in J-labelings. There are many open problems that remain to be solved, we end the paper by presenting some of them. 2 Distance /-labelings We start this section by providing the labeling length of some well-known families of graphs. By definition, A(Ki) = 0. In what follows, we only consider graphs of order at least 2. Proposition 2.1. Let n > 2. The complete graph Kn has A(Kn) = 1. Proof. By assigning the label 1 to all vertices of Kn, we obtain a distance 1-labeling of it. □ Proposition 2.2. Let n > 2. The path Pn has A(Pn) = |_n/2_|. Proof. By a previous comment, we know that a Skolem sequence of order m exists if m = 0 or 1 (mod 4). This fact together with (1.1) guarantees the existence of a proper distance |n/2j -labeling when n = 4,6 (mod 8). By removing one of the end labels of (1.1), we obtain a (non proper) distance labeling of length |_n/2j. Thus, we have that A(Pn) < |_n/2j. Since there are no three vertices in the path which are at the same distance, this lower bound turns out to be an equality. □ The sequence that appears in (1.1) also works for constructing proper distance labelings of cycles. Thus, we obtain the next result. 238 Ars Math. Contemp. 12 (2017) 383-413 Proposition 2.3. Let n > 3. The cycle Cn has A(C„) = | (n — 2)/2, n = 6, n is divisible by 6, |_n/2j, otherwise. Proof. Since, except for n divisible by 3, there are no three vertices in the cycle Cn which are at the same distance, we have that A(Cn) > |_n/2j. The sequence that appears in (1.1) allows us to construct a (proper) distance |_n/2j -labeling of Cn when n is odd. Moreover, if n even not divisible by 3 we can obtain a distance |_n/2j -labeling of Cn from the sequence that appears in (1.1) just by removing the end odd label. Suppose now that n is divisible by 3. If n is odd or n = 6, at least |_n/2j labels are needed to obtain a distance labeling of Cn. Thus, A(Cn) = |_n/2j. So, in what follows we will assume that n is divisible by 6. Since there are three vertices in the cycle which are at the same distance, we have that A(Cn) > (n — 2)/2. Let pm and qm be the largest even and odd numbers, respectively, not exceeding (n — 2)/2. If n = 0,4 (mod 8) then the sequence (pm,pm — 2,..., 2, qm, 2,... ,pm — 2,pm, 0, qm — 2, qm — 4,..., 3, qm, n/3,3,5,..., qm — 2,1,1) defines a (proper) distance (n — 2)/2-labeling of Cn. If n = 6 (mod 8) then (pm — 2,pm — 4,..., 2,pm, 2,... ,pm — 4,pm — 2,0, qm, qm — 2,..., 3, pm, n/3, 3, 5,..., qm — 2, qm, 1,1) defines a (proper) distance (n — 2)/2-labeling of Cn. Finally, if n = 2 (mod 8), then the sequence (pm,pm—2,..., 2, n/6+ [n/12], 2, ...,pm,n/6+ [n/12],qm,qm — 2,.. ., n/6 + |~n/12] +2,n/6+ |~n/12] — 2, n/6+ [n/12] —4,.. ., 3, 0, n/3, 3, 5, ..., n/6+ [n/12] —2,1,1, n/6+ [n/12] +2, n/6+ [n/12] + 4,..., qm) defines a (proper) distance (n — 2)/2-labeling of Cn. □ Proposition 2.4. The star Ki,k has A(Ki,k) = 2 when k > 3, and A(Ki,k) = 1 otherwise. Proof. For k > 3, consider a labeling f that assigns the label 1 to the central vertex and to one of its leaves, and that assigns label 2 to the other vertices. Then f is a (proper) distance 2-labeling of K1,k. For 1 < k < 2, the sequences 1 — 1 and 0 — 1 — 1, where 0 is assigned to a leaf, give a (proper) distance 1-labeling of K1,1 and K1,2, respectively. □ Proposition 2.5. Let m and n be integers with 2 < m < n. Then, A(Km,n) = m. In particular the graph Kmn admits a proper distance l-labeling if and only if m g {1, 2}. Proof. Let X and Y be the stable sets of Km,n, with |X | = m and |Y| = n. We have that D(Km n) = 2, however the maximum number of vertices that are mutually at distance 2 is n. Thus, by assigning label 2 to all vertices, except one, in Y, 1 to the remaining vertex in Y and to one vertex in X, 0 to another vertex of X we still have left m — 2 vertices in X to label. □ Proposition 2.6. Let n and k be positive integers with n > 2 and k > 3. Let Sn be the graph obtained from K1,k by replacing each edge with a path of n edges. Then Moreover, for k < n — 1, the graph Sn admits an l-distance labeling, where 2(n — o) < l < 2(n — o) + 1, and |(2n — 1)/(2k + 1)j < o < |_(2n + 2)/(2k + 1)j. S. C. Lopez and F. A. Muntaner-Batle: Distance labelings 239 Proof. Suppose that S? admits a distance l-labeling with l < 2n. Then, all the labels assigned to leaves should be different and they appear at most twice. Moreover, although each even label could appear k-times, one for each of the k paths that are joined to the star Kijfc, odd labels also appear at most twice (either in the same or in two of the original forming paths). Thus, once we fix the labels of leaves, we still have to assign a label to at least (k - 2)(n - 2) + 1 vertices. Thus, at least 2n - 2 labels are needed for obtaining a distance labeling of S?, when k > n - 1. The following construction provides a distance 2(n - 1)-labeling of S?, when k = n - 1. Suppose that we label the central vertices of each path using the pattern 2 - 4 - ... - 2(n - 1). Then, add odd labels to the leaves. For the case k = n, we need to introduce a new odd label, which corresponds to 2n - 1. Finally, when k > n, we cannot complete a distance l-labeling without using 2n labels. Fig. 1 provides a proper 2n-labeling that can be generalized in that case. The case k < n -1 requires a more detailed study. Consider the labeling of S? obtained by assigning the labels in the sequence 0 - 2 - 4 - ... - 2(n - o) - si - s| - ... - sO to the vertices of the path P\ i = 1,..., k, where 0 is the label assigned to the central vertex of S?, and {sjis the (multi)set of odd labels, if necessary, we replace some of the even labels by the remaining odd labels. By considering the patern 1 - 1, 3 - 1 - 1 - 3, 5 - 3 - 1 - 1 - 3 - 5 to the vertices of one of the paths, it can be checked that, the graph S? admits an l-distance labeling with l g {2(n - o), 2(n - o) + 1} and 2n - 1 2k + 1 , 2n + 2, ^o ^ j. More specifically, if l(2n - 1)/(2k + 1)j = |_(2n + 2)/(2k + 1)j then o = |_(2n -1)/(2k + 1)j and l = 2(n - o). If |_(2n - 1)/(2k + 1)j + 1 = |_(2n)/(2k + 1)j then o = |(2n)/(2k+1)j and l = 2(n-o) + 1. Finally, if |(2n)/(2k +1)j+1 = |(2n+1)/(2k +1)j then o = l(2n +1)/(2k + 1)j and l = 2(n - o) + 1. □ Fig. 2 and Fig. 3 show proper distance labelings of S| and Sf, respectively, that have been obtained by using the above constructions, and then, combining pairs of paths (whose end odd labels sum up to 8) for obtaining a proper distance 8-labeling and 9-labeling, respectively. 10 10 9 7 5 3 1 2 4 6 8 10 10 8 6 4 2 2 4 6 8 10 9 7 5 3 1 2 4 6 8 Figure 1: A proper distance 10-labeling of Sf. Proposition 2.7. For n > 3, let Wn be the wheel of order n +1. Then A(Wn) = [n/2]. Proof. Except for W3, all wheels have D(Wn) = 2. The maximum number of vertices that are mutually at distance 2 is |n/2j and all of them are in the cycle. Thus, by assigning 240 Ars Math. Contemp. 12 (2017) 383-413 1 1 6 7 2 2 4 6 " ' " ' 8 5 3 8 6 3 2 2 4 6 8 7 Figure 2: A proper distance 8-labeling of S|. 1 1 9 7 2 2 4 6 8 5 3 8 6 3 4 6 8 7 246 8 9 Figure 3: A proper distance 9-labeling of Sf. label 2 to all these vertices, 0 to one vertex of the cycle and 1 to the central vertex and to one vertex of the cycle, we still have to label [n/2] - 2 vertices. Proposition 2.8. For n > 2, let Fn be the fan of order n + 1. Then A(Fn) = |_n/2j. Proof. Except for F2, all fans have D(Fn) = 2. The maximum number of vertices that are mutually at distance 2 is [n/2] and all of them are in the path. Thus, by assigning label 2 to all these vertices, 0 to one vertex of the path, 1 to the central vertex and to one vertex of the path when n is even and to two vertices when n is odd, we still have to label | n/2j - 2 vertices. 2.1 The inverse problem For every positive integer l, there exists a graph G of order l with a trivial l-labeling that assigns a different label in [1, l] to each vertex. In this section, we are interested in the existence of a graph G that admits a proper distance l-labeling. We are now ready to state and prove the next result. Theorem 2.9. For every pair of positive integers l and r, r > 2, there exists a graph G of order lr with a regular l-labeling of degree r. Proof. We give a constructive proof. Assume first that l is odd. Let G be the graph obtained from the complete graph Kr by identifying r -1 vertices of Kr with one of the end vertices of a path of length |l/2j and the remaining vertex of Kr with the central vertex of the graph . That is, G is obtained from Kr by attaching 2r paths of length |l/2j to its vertices, r + 1 to a particular vertex v1 of Kr and exactly one path to each of the remaining vertices F = {v2, v3,..., vr} of Kr. Now, consider the labeling f of G that assigns 1 to the vertices of Kr, the sequence 1 - 3 - ... - l to the vertices of the paths attached to F and one of the paths attached to v1, and the sequence 1 - 2 - 4 - ... - (l - 1) to the remaining paths. Then f is a regular l-labeling of degree r of G. Assume now that l is even. Let G be the graph obtained in the above construction for l - 1. Then, by adding a leaf to each S. C. Lopez and F. A. Muntaner-Batle: Distance labelings 241 vertex of G labeled with I - 2 we obtain a new graph G' that admits a regular l-labeling f' of degree r. The labeling f' can be obtained from the labeling f of G, defined above, just by assigning the label I to the new vertices. □ Figure 4: A regular 5-labeling of degree 4 of a graph G. Figure 5: A regular 6-labeling of degree 4 of a graph G'. Notice that, the graph provided in the proof of Theorem 2.9 also has A(G) = l. Figs 4 and 5 show examples for the above construction. The pattern provided in the proof of the above theorem, for r = 2, can be modified in order to obtain the following lower bound for the size of a graph G as in Theorem 2.9. Proposition 2.10. For every positive integer l there exists a graph of order 2l and size (l + 2)(l +1)/2 — 2 that admits a regular distance l-labeling of degree 2. Proof. Let G be the graph of order 2l and size (l + 1)l/2 +1 — 1, obtained from Ki+1 and the path Pi by identifying one of the end vertices u of Pi with a vertex v of Ki+1. Let f be the labeling of G that assigns the sequence 1 — 2 — 3 — ... — l to the vertices of Pi and 1 — 1 — 2 — ... — l to the verticalces of Ki+1 in such a way that the vertex obtained by identifying u and v is labeled 1. Then, f is a 2-regular l-labeling of G. □ Thus, a natural question appears. 242 Ars Math. Contemp. 12 (2017) 383-413 Question 2.11. Can we find graphs that admit a regular distance 1-labeling of degree 2 which have bigger density (where by density we refer the number of edges in relation to the number of vertices) than the one of Proposition 2.10? We end this section by introducing an open question related to complexity. Question 2.12. What is the algorithmic complexity of computing A(G) for a general graph G? What about for a tree? 3 Distance J-labelings It is clear from the definition that to say that a graph admits a (proper) distance 1-labeling is the same as to say that the graph admits either a (proper) distance [0,1]-labeling or a (proper) distance [1, 1]-labeling. That is, we relax the condition on the labels, the set of labels is not necessarily a set of consecutive integers. In this section, we study which kind of sets J can appear as the set of labels of a graph that admits a distance J-labeling. The following easy fact is obtained from the definition. Lemma 3.1. Let G be a graph with a proper distance J-labeling f. Then J C [0, D(G)], where D(G) is the diameter of G. 3.1 The inverse problem: distance J-labelings obtained from sequences. We start with a definition. Let S = (si, si,..., si, s2,..., s2,..., «i,..., si) be a sequence of nonnegative integers where, (i) sj < sj whenever i < j and (ii) each number sj appears kj times, for i = 1,2,..., 1. We say that S is a S-sequence if there is a simple graph G that admits a partition of the vertices V(G) = uj=1 Vj such that, for all i G {1, 2,..., 1}, |V | = kj, and if u, v G Vj then dG(u, v) = sj. The graph G is said to realize the sequence S. Let E = {s1 < s2 < ... < si} be a set of nonnegative integers. We say that E is a S-set with n degrees of freedom or a Sn-set if there is a S-sequence S of the form S = (s1, s1,..., s1, s2,..., s2,..., si,..., si), in which the following conditions hold: (i) all, except n numbers different from zero, appear at least twice, and (ii) if si = 0 then 0 appears exactly once in S. We say that any graph realizing S also realizes E. If n = 0 we simply say that E is a S-set. Let us notice that an equivalent definition for a S-set is the following: E is a S-set if there exists a graph G that admits a proper distance E-labeling. Proposition 3.2. Let E = {1 = s1 < s2 < ... < si} be a set such that sj — sj-1 < 2, for i = 1, 2,..., 1. Then E is a S-set. Furthermore, there is a caterpillar of order 21 that realizes E. Proof. We claim that for each set E = {1 = s1 < s2 < ... < si} such that sj — sj-1 < 2 there is a caterpillar of order 21 that admits a 2-regular distance E-labeling in which the label si is assigned to exactly two leaves. The proof is by induction on 1. For 1 = 1, the path P2 admits a 2-regular distance {1}-labeling, and for 1 = 2, the star K13 and the path P4 admit a 2-regular distance {1,2}-labeling and a 2-regular distance {1, 3}-labeling, respectively. Assume that the claim is true for 1 and let E = {1 = s1 < s2 < ... < si+1} such that sj — sj-1 < 2. Let E' = E \ {si+1}. By the induction hypothesis, there is a caterpillar G' of order 21 that admits a regular distance E'-labeling of degree 2 in which the label si is assigned to leaves, namely, u1 and u2. Let u G V(G') be the (unique) vertex S. C. Lopez and F. A. Muntaner-Batle: Distance labelings 243 in G adjacent to ui. Then, if s;+1 - s; = 2, the caterpillar obtained from G by adding two new vertices v1 and v2 and the edges UjVj, for i = 1,2, admits a regular distance S-labeling of degree 2 in which the label s;+1 is assigned to leaves {v1, v2}. Otherwise, if sl+1 - s; = 1 then the caterpillar obtained from G by adding two new vertices v1 and v2 and the edges uv1 and u2v2 admits a regular distance S-labeling of degree 2 in which the label s;+1 is assigned to leaves {v1, v2}. This proves the claim. To complete the proof, we only have to consider the vertex partition of G defined by the vertices that receive the same label. □ Proposition 3.2 provides us with a family of ¿-sets, in which, if we order the elements of each ¿-set, we get that the differences between consecutive elements are at most 2. This fact may lead us to get the idea that the differences between consecutive elements in ¿-sets cannot be too large. This is not true in general and we show it in the next result. Theorem 3.3. Let {k1, k2,..., kn} be a set of positive integers. Then there exists a ¿-set S = {s1 3. Thus, in fact, Proposition 3.4 can be generalized as follows. Proposition 3.5. The set S = {2, n} is not a ¿-set. 245 Ars Math. Contemp. 12 (2017) 383-413 Notice that, although E = {2, n} is not a ¿-set, it is a ¿i-set, since we can consider a star in which the center is labeled with n and the leaves with 2. The next result gives a lower bound on the size of ¿-sets in terms of the maximum of the set. Theorem 3.6. Let E be a ¿-set with s = max E. Then, |E| > |"(s + 1)/2], Proof. Let G be a graph that realizes E and let V(G) = uieSVj be the partition defined as follows: if u, v e V then dG(u,v) = i. Let a1,a2 g Vs. At this point, let P = b1b2.. .bs+1 be a path of length s starting at a1 and ending at a2. We claim that there are no three vertices in V(P) belonging to the same set Vj, j e E. Assume to the contrary that there exist vertices u, v and w e V(P) such that dG(u, v) = dG(u, w) = dG(v, w). Then, we also obtain that dP(u, v) = dP(v, w) = dP(v, w) (since they are on a shortest path between two points), a contradiction. Hence, each set in the partition of V(G) can contain at most two vertices of P. Since |V(P)| = s + 1, it follows that we need at least |"(s +1)/2] sets in the partition of V (G). Therefore, we obtain that |E| > |"(s + 1)/2]. □ It is clear that the above proof cannot be improved in general, since from Proposition 3.2 we get that the any set of the form {1,3, 5,..., 2n + 1} is a ¿-set and |{1,3, 5,..., 2n + 1}| = |"(2n + 2)/2]. Furthermore, Proposition 3.5 for n > 4 is an immediate consequence of the above result. It is also worth to mention that there are sets which meet the bound provided in Theorem 3.6, however they are not ¿-sets. For instance, the set {2,3} considered in Proposition 3.4. From this fact, it seems that we cannot characterize ¿-sets just from a density point of view. Next we want to propose the following open problem. Problem 3.7. Characterize ¿-sets. Let E be a set. By construction, a path of order |E| in which each vertex receives a different labeling of E defines a distance |E|-labeling. That is, every set is a ¿|S|-set. So, according to that, we propose the next problem. Problem 3.8. Given a set E is there a construction that provides the minimum r such that E is a ¿r-set? Thus, the above problem is a bit more general than Open problem 3.7. Acknowledgement The authors thank the anonymous referee for the valuable suggestions that helped to improve the quality of the paper. In particular, the authors are highly indebted to the referee for her/his suggestion on the proof of Proposition 2.3. References [1] J. Abrham and A. Kotzig, Skolem sequences and additive permutations, Discrete Math. 37 (1981), 143-146. [2] J. C. Bermond, A. E. Brouwer and A. Germa, Systemes de triples et differences associees, in: Proc. Colloque C.N.R.S. - Problèmes combinatoires et théorie des graphes., Orsay, 1976 pp. 35-38. [3] N. Francetic and E. Mendelsohn, A survey of Skolem-type sequences and Rosa's use of them, Math. Slovaca 59 (2009), 39-76. S. C. Lopez and F. A. Muntaner-Batle: Distance labelings 70 [4] C. D. Langford, Problem, Math. Gaz. 42 (1958), 228. [5] S. C. LOpez and F. A. Muntaner-Batle, Langford sequences and a product of digraphs, European J. Combin. 53 (2016), 86-95. [6] M. Mata-Montero, S. Normore and N. Shalaby, Generalized Langford sequences: new results and algorithms, Int. Math. Forum 9 (2014), 151-181. [7] S. Mor and V. Linek, Hooked extended Langford sequences of small and large defects, Math. Slovaca 64 (2014), 819-842. [8] R. S. Nickerson and D. C. B. Marsh, Problems and Solutions: Solutions of Elementary Problems: E1845, Amer. Math. Monthly 74 (1967), 591-592. [9] N. Shalaby and D. Silvesan, The intersection spectrum of Skolem sequences and its applications to -fold cyclic triple systems, Discrete Math. 312 (2012), 1985-1999. [10] N. Shalaby and D. Silvesan, The intersection spectrum of hooked Skolem sequences and applications, Discrete Appl. Math. 167 (2014), 239-260. [11] J. E. Simpson, Langford sequences: perfect and hooked, Discrete Math. 44 (1983), 97-104. [12] T. Skolem, On certain distributions of integers into pairs with given differences, Math. Scand. 5 (1957), 57-68. [13] T. Skolem, Some remarks on the triple systems of Steiner, Math. Scand. 6 (1958), 273-280. [14] W. D. Wallis, Magic graphs, Birkhauser, Boston, 2001. [15] D. B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.