ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.22530 J. Algebra Comb. Discrete Appl. 3(3) • 159–164 Received: 07 December 2015 Accepted: 19 March 2016 Journal of Algebra Combinatorics Discrete Structures and Applications Regular handicap tournaments of high degree Research Article Dalibor Froncek, Aaron Shepanik Abstract: A handicap distance antimagic labeling of a graph G = (V, E) with n vertices is a bijection f : V → {1, 2, . . . , n} with the property that f(xi) = i and the sequence of the weights w(x1), w(x2), . . . , w(xn) (where w(xi) = ∑ xj∈N(xi) f(xj)) forms an increasing arithmetic progression with difference one. A graph G is a handicap distance antimagic graph if it allows a handicap distance antimagic labeling. We construct (n−7)-regular handicap distance antimagic graphs for every order n ≡ 2 (mod 4) with a few small exceptions. This result complements results by Kovář, Kovářová, and Krajc [P. Kovář, T. Kovářová, B. Krajc, On handicap labeling of regular graphs, manuscript, personal communication, 2016] who found such graphs with regularities smaller than n−7. 2010 MSC: 05C78 Keywords: Incomplete tournaments, Handicap tournaments, Distance magic labeling, Handicap labeling 1. Motivation The study of handicap distance antimagic graphs has been motivated by incomplete round-robin type tournaments with various properties. A complete round robin tournament of n teams is a tournament in which every team plays the remaining n−1 teams. When the teams are ranked 1, 2, . . . ,n according to their strength, it is apparent that the sum of rankings of all opponents of the i-th ranked team, denoted w(i), is w(i) = n(n + 1)/2−i, and the sequence w(1),w(2), . . . ,w(n) is a decreasing arithmetic progression with difference one. Because complete round robin tournaments are generally considered to be fair, a tournament of n teams in which every team plays precisely r opponents, where r < n − 1 and the sequence w(1),w(2), . . . ,w(n) is a decreasing arithmetic progression with difference one is called a fair incomplete round robin tournament. A disadvantage of such a tournament is that the best team plays the weakest opponents, while the weakest team plays the strongest opponents. This disadvantage is eliminated in equalized incomplete round robin tournaments in which the sum of rankings of all opponents of every team is the same. Some results on fair incomplete round robin tournaments can be found in [6] and [3]. Dalibor Froncek (Corresponding Author), Aaron Shepanik; Department of Mathematics and Statistics, University of Minnesota Duluth, USA (email: dfroncek@d.umn.edu, shepa107@d.umn.edu). 159 D. Froncek, A. Shepanik / J. Algebra Comb. Discrete Appl. 3(3) (2016) 159–164 However, if we want to give the weaker teams a better chance of winning, the weakest team should play the weakest opponents, while the strongest one should play the strongest opponents. That is, the sequence w(1),w(2), . . . ,w(n) should be an increasing arithmetic progression. A tournament in which this condition is satisfied, and every team plays r < n− 1 games, is called a handicap incomplete round robin tournament. The existence of such tournaments with n ≡ 0 (mod 4) is studied by the authors in [D. Froncek and A. Shepanik, Handicap incomplete tournaments of order n ≡ 0 (mod 4), manuscript, personal com- munication, 2016], Kovář [P. Kovář, On regular handicap graphs, personal communication, June 16, 2016] and Kovářová [T. Kovářová, On regular handicap graphs, personal communication, June 16, 2016]. Kovář, Kovářová, and Krajc [P. Kovář, T. Kovářová, B. Krajc, On handicap labeling of regular graphs, manuscript, personal communication, 2016] found such tournaments for n ≡ 2 (mod 4) and r ≤ n− 11 and proved that they can exist only when r is odd and at most n − 7. We provide a construction of handicap incomplete round robin tournaments for n ≡ 2 (mod 4) and the missing regularity r = n− 7 with a few small exceptions. 2. Basic notions By a graph G = (V,E) we mean a finite undirected graph without loops or multiple edges. For graph theoretic terminology we refer to Chartrand and Lesniak [2]. Motivated by properties of magic squares, Vilfred [12] introduced the concept of sigma labelings. The same concept was introduced by Miller et al. [10] under the name 1-vertex magic vertex labeling. Sugeng et al. [11] introduced the term distance magic labeling, which currently seems to be most commonly used. A survey on distance magic graphs was published recently [1]. Many newer results can by found in an extensive survey with much wider focus by Gallian [7]. Definition 2.1. A distance magic labeling of a graph G of order n is a bijection f : V → {1, 2, . . . ,n} with the property that there is a positive integer µ such that ∑ y∈N(x) f(y) = µ for every x ∈ V. The constant µ is called the magic constant of the labeling f. The sum ∑ y∈N(x) f(y) is called the weight of the vertex x and is denoted by w(x). When we think of the vertices as of teams and identify their labels with their rankings, we can see that a distance magic graph is providing a structure of a fair incomplete tournament described above. In [4] the first author introduced two closely related concepts, namely the distance antimagic and handicap distance antimagic labelings (which was called an ordered distance antimagic labeling in that paper) and showed their relationship to certain types of incomplete round robin tournaments. The term “handicap distance antimagic labeling” was originally coined by Kovářová [T. Kovářová, On regular handicap graphs, personal communication, June 16, 2016]. Definition 2.2. A distance d-antimagic labeling of a graph G = (V,E) with n vertices is a bijection f : V → {1, 2, . . . ,n} with the property that there exists an ordering of the vertices of G such that the sequence of the weights w(x1),w(x2), . . . ,w(xn) forms an arithmetic progression with difference d. When d = 1, then f is called just distance antimagic labeling. A graph G is a distance d-antimagic graph if it allows a distance d-antimagic labeling, and a distance antimagic graph when d = 1. It should be obvious that a graph G is distance magic if and only if its complement G is distance antimagic. In distance antimagic graphs the weight of a vertex is not tied to its own label. All that we require is that the sequence w(x1),w(x2), . . . ,w(xn) forms an arithmetic progression. We now impose an additional condition on the labeling and require that a vertex with a lower label has a lower weight than a vertex with a higher label. 160 D. Froncek, A. Shepanik / J. Algebra Comb. Discrete Appl. 3(3) (2016) 159–164 Definition 2.3. A handicap distance d-antimagic labeling of a graph G = (V,E) with n vertices is a bijection f : V → {1, 2, . . . ,n} with the property that f(xi) = i and the sequence of the weights w(x1),w(x2), . . . ,w(xn) forms an increasing arithmetic progression with difference d. When d = 1, the labeling is called just a handicap distance antimagic labeling (or a handicap labeling for short). A graph G is a handicap distance d-antimagic graph if it allows a handicap distance d-antimagic labeling, and a handicap distance antimagic graph or a handicap graph when d = 1. Again, if we identify each team in a tournament with its ranking, then an r-regular handicap distance d-antimagic graph is nothing else than a model of a handicap incomplete round robin tournament, since the sum of rankings of opponents of team i is its weight w(i) and the sequence of weights is an increasing arithmetic progression. Our constructions will be based on the properties of magic rectangles, which are a generalization of the magic squares mentioned above. Definition 2.4. A magic rectangle MR(a,b) is an a × b array whose entries are 1, 2, . . . ,ab, each ap- pearing once, with all row sums equal to a constant ρ and all column sums equal to a constant σ. It is easy to observe that a and b must be either both even or both odd. The following existence result was proved by Harmuth [8, 9] more than 130 years ago. Theorem 2.5. [8, 9] A magic rectangle MR(a,b) exists if and only if a,b > 1, ab > 4, and a ≡ b (mod 2). 3. Known results Kovář, Kovářová, and Krajc [P. Kovář, T. Kovářová, B. Krajc, On handicap labeling of regular graphs, manuscript, personal communication, 2016], Kovář [P. Kovář, On regular handicap graphs, per- sonal communication, June 16, 2016] and Kovářová [T. Kovářová, On regular handicap graphs, personal communication, June 16, 2016] proved the following results. Theorem 3.1. Let G be an r-regular handicap graph on n vertices, where n ≡ 2 (mod 4). Then r ≡ 3 (mod 4) and r ≤ n− 7. Theorem 3.2. For n ≡ 2 (mod 4), there exists an r-regular handicap graph if 3 ≤ r ≤ n− 11 and r ≡ 3 (mod 4) except when r = 3 and n ≤ 26. Their result leaves open the case of n ≡ 2 (mod 4) and r = n−7 for n ≥ 14. In the following section, we prove the existence of such graphs with the exception of n = 14, 18, 22, 26, 34, 38, which remain in doubt. In our constructions, we will also use the following result by Kovář [P. Kovář, On regular handicap graphs, personal communication, June 16, 2016] and Kovářová [T. Kovářová, On regular handicap graphs, personal communication, June 16, 2016]. Theorem 3.3. For n ≡ 0 (mod 4) there exists an (n− 7)-regular handicap graph whenever n ≥ 16. In [5] the first author made made an observation, which was a special case of the following. Observation 3.4. Let G be an r-regular distance 2-antimagic graph with vertices x1,x2, . . . ,xn, labeling f and weight function w such that f(xi) = i and w(xi) = k − 2i for some constant k. Then G, the complement of G, is an (n− r − 1)-regular handicap graph with labeling f and weight function w such that w(xi) = n(n + 1)/2 −k + i. The converse is obviously also true. Proof. Label the vertices of the complete graph Kn so that vertex xi is labelled i. The sum of labels of all neighbors of xi is then indeed equal to n(n + 1)/2− i. Every neighbor of xi contributes its label to 161 D. Froncek, A. Shepanik / J. Algebra Comb. Discrete Appl. 3(3) (2016) 159–164 either w(xi) or w(xi). Therefore, we have w(xi) + w(xi) = n(n + 1)/2 − i and w(xi) = n(n + 1)/2 − i−w(xi). Because w(xi) = k − 2i, it follows that w(xi) = n(n + 1)/2 − i− (k − 2i) = n(n + 1)/2 −k + i. This completes the proof. We will use the observation in our constructions and instead of constructing directly (n−7)-regular handicap graphs, we will construct 6-regular distance 2-antimagic graphs satisfying assumptions of Ob- servation 3.4. We will call such graphs genuine distance 2-antimagic graphs and the labeling will be called a genuine distance 2-antimagic labeling. The following observation was proved in a more general form in [4]. To avoid introduction of a new notion that would be only used in its special form, we state the observation as follows. Observation 3.5. [4] The graph G = Ka�Kb admits a genuine distance 2-antimagic labeling f such that f(x) = p implies w(x) = (a + b)(ab + 1)/2 − 2p for every x ∈ V (G) whenever there exists a magic rectangle MR(a,b). 4. New results Lemma 4.1. There exists a 6-regular genuine distance 2-antimagic graph on 12 vertices. Proof. Let G = K2�K6. By Theorem 2.5 there exist a magic rectangle MR(2, 6). The assertion follows directly from Observation 3.5. Lemma 4.2. There exists a 6-regular genuine distance 2-antimagic graph H on 30 vertices. Proof. We denote the vertices of H by yst and zst for 1 ≤ s ≤ 3 and 1 ≤ t ≤ 5. The edge set will consist of edges ystypt, zstzpt, and ystzsq for every for every 1 ≤ s ≤ p ≤ 3 and 1 ≤ t ≤ 5 with t 6= q. Let MR(3, 5) be a 3 × 5 magic rectangle with entries mst for 1 ≤ r ≤ 3 and 1 ≤ s ≤ 5. We label the vertices yst by entries mst in the natural way, that is, f(yst) = mst while the vertices zst obtain the labels raised by 15, that is, f(zst) = mst + 15. Notice that the vertices yst have the highest weights. We now rename the vertices so that vertex yst or zst becomes xi when w(yst) = 124−2i or w(zst) = 124 − 2i, respectively. One can check that this labeling has the required property and H is a 6-regular genuine distance 2-antimagic graph. Now we are ready to present our construction. Lemma 4.3. There exists a 6-regular genuine distance 2-antimagic graph G on n vertices for every n ≡ 2 (mod 4) and n ≥ 42. Proof. We use two building blocks, graph H on 30 vertices from the previous Lemma, and a graph J on m ≡ 0 (mod 4) vertices whose existence is guaranteed by Lemma 4.1 and Theorem 3.3. Our graph G will then have n = m + 30 vertices. Let H be the graph on 30 vertices constructed in Lemma 4.2 with vertices x1,x2, . . . ,x30, genuine distance 2-antimagic labeling fH and vertex weights wH satisfying fH (xi) = i and wH (xi) = 124 − 2i. 162 D. Froncek, A. Shepanik / J. Algebra Comb. Discrete Appl. 3(3) (2016) 159–164 It follows from Theorem 3.3 and Observation 3.4 that for any m ≡ 0 (mod 4) there exists a genuine distance 2-antimagic labeling graph J with vertices u1,u2, . . . ,um, labeling fJ and vertex weights wJ satisfying fJ (uj) = j and wJ (uj) = 4m− 2j. We use H and J as components of G and rename the vertices so that xi becomes vi for i = 1, 2, . . . , 15, uj becomes vj+15 for j = 1, 2, . . . ,m and xi becomes vi+m for i = 16, 17, . . . , 30. Then we label all vertices using labeling function fG as fG(vi) = i to obtain the desired genuine distance 2-antimagic labeling. We can check that for i = 1, 2, . . . , 15 we have wG(vi) = wH (xi) + 4m = 124 − 2i + 4m = 4(m + 30) + 4 − 2i = 4n + 4 − 2i, because vi has two neighbors in the “lower” part of H (that is, among vertices v1,v2, . . . ,v15) where the labels have not changed, and four neighbors in the “upper” part (among vertices vm+16,vm+17, . . . ,vm+30), where each label was increased by m. For i = 16, 17, . . . ,m + 15 we have wG(vi) = wJ (ui−15) + 90 = 4m + 4 − 2(i− 15) + 90 = 4(m + 30) + 4 − 2i = 4n + 4 − 2i, because the labels of all six neighbors were increased by 15. Finally, for i = m + 16,m + 17, . . . ,m + 30 we have wG(vi) = wH (xi−m) + 2m = 124 − 2(i−m) + 2m = 4(m + 30) + 4 − 2i = 4n + 4 − 2i, because vi has four neighbors in the “lower” part of H where the labels have not changed, and two neighbors in the “upper” part where each label was increased by m. Our main result now follows directly from Lemma 4.3 and Observation 3.4. Theorem 4.4. For n ≡ 2 (mod 4), there exists an (n − 7)-regular handicap graph when n = 30 or n ≥ 42. This, together with the result by Kovář [P. Kovář, On regular handicap graphs, personal communi- cation, June 16, 2016] and Kovářová [T. Kovářová, On regular handicap graphs, personal communication, June 16, 2016], gives an almost complete characterization of handicap graphs for n ≡ 2 (mod 4). Theorem 4.5. For n ≡ 2 (mod 4), there exists an r-regular handicap graph if and only if 3 ≤ r ≤ n− 7 and r ≡ 3 (mod 4) except when r = 3 and n ≤ 26 and possibly when r = n − 7 and n ∈ {14, 18, 22, 26, 34, 38}. Since no magic rectangles of orders 14, 22, 26, 34, or 38 exist, one has to hope that a computer aided search would help to settle the existence question for these orders. A construction for n = 18 similar to that for n = 30 may exist, but the authors were unable to find one. References [1] S. Arumugam, D. Froncek, N. Kamatchi, Distance magic graphs – a survey, J. Indones. Math. Soc. Special Edition (2011) 1–9. [2] G. Chartrand, L. Lesniak, Graphs and Digraphs, Chapman and Hall, CRC, Fourth edition, 2005. [3] D. Froncek, Fair incomplete tournaments with odd number of teams and large number of games, Congr. Numer. 187 (2007) 83–89. [4] D. Froncek, Handicap distance antimagic graphs and incomplete tournaments, AKCE Int. J. Graphs Comb. 10(2) (2013) 119–127. [5] D. Froncek, Handicap incomplete tournaments and ordered distance antimagic graphs, Congr. Nu- mer. 217 (2013) 93–99. 163 http://www.ams.org/mathscinet-getitem?mr=3082443 http://www.ams.org/mathscinet-getitem?mr=3082443 http://www.ams.org/mathscinet-getitem?mr=2408780 http://www.ams.org/mathscinet-getitem?mr=2408780 http://www.ams.org/mathscinet-getitem?mr=3114157 http://www.ams.org/mathscinet-getitem?mr=3114157 http://www.ams.org/mathscinet-getitem?mr=3220296 http://www.ams.org/mathscinet-getitem?mr=3220296 D. Froncek, A. Shepanik / J. Algebra Comb. Discrete Appl. 3(3) (2016) 159–164 [6] D. Froncek, P. Kovář, T. Kovářová, Fair incomplete tournaments, Bull. Inst. Combin. Appl. 48 (2006) 31–33. [7] J. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (# DS6) (2015) 43 pp. [8] T. Harmuth, Ueber magische Quadrate und ähnliche Zahlenfiguren, Arch. Math. Phys. 66 (1881) 286–313. [9] T. Harmuth, Ueber magische Rechtecke mit ungeraden Seitenzahlen, Arch. Math. Phys. 66 (1881) 413–447. [10] M. Miller, C. Rodger, R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2003) 305–315. [11] K. A. Sugeng, D. Froncek, M. Miller, J. Ryan, J. Walker, On distance magic labeling of graphs, J. Combin. Math. Combin. Comput. 71 (2009) 39–48. [12] V. Vilfred, Σ-labelled graph and circulant graphs, Ph.D. Thesis, University of Kerala, Trivandrum, India, 1994. 164 http://www.ams.org/mathscinet-getitem?mr=2259699 http://www.ams.org/mathscinet-getitem?mr=2259699 http://www.ams.org/mathscinet-getitem?mr=1668059 http://www.ams.org/mathscinet-getitem?mr=1999203 http://www.ams.org/mathscinet-getitem?mr=1999203 http://www.ams.org/mathscinet-getitem?mr=2568905 http://www.ams.org/mathscinet-getitem?mr=2568905 Motivation Basic notions Known results New results References