Electronic Journal of Graph Theory and Applications 6 .
, 208Ae218 Regular handicap graphs of order n O 0 .
Dalibor Froncek.
Aaron Shepanik Department of Mathematics and Statistics University of Minnesota Duluth Duluth.
USA dalibor@d.
edu, shepa107@d.
Abstract A handicap distance antimagic labeling of a graph G = (V.
E) with n vertices is a bijection fI : V Ie .
, 2, .
, .
with the property that fI.
i ) = i, the weight w.
i ) is the sum of labels of all neighbors of xi , and the sequence of the weights w.
1 ), w.
2 ), .
, w.
n ) forms an increasing arithmetic progression.
A graph G is a handicap distance antimagic graph if it allows a handicap distance antimagic labeling.
We construct r-regular handicap distance antimagic graphs of order n O 0 .
for all feasible values of r.
Keywords: graph labeling, handicap labeling, regular graphs, tournament scheduling Mathematics Subject Classification : 05C78 DOI: 10.
5614/ejgta.
Introduction The study of handicap distance antimagic graphs was motivated by incomplete round-robin type tournaments that possess various properties.
A complete round robin tournament of n teams is a tournament in which every team plays each of the remaining n Oe 1 teams.
Since each team plays every other team, complete round robin tournaments are sometimes considered fair tournaments.
When the teams are ranked 1, 2, .
, n according to their standings, then the sum of rankings of all opponents of the i-th ranked team, called weight and denoted w.
, is w.
= n.
/2 Oe i, and the sequence w.
, w.
, .
, w.
is a decreasing arithmetic progression with difference one.
A tournament of n teams in which Received: 25 November 2017.
Revised: 9 March 2018.
Accepted: 8 April 2018.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik every team plays precisely r opponents, where r < n Oe 1 and the sequence w.
, w.
, .
, w.
is a decreasing arithmetic progression with difference one is called a fair incomplete round robin tournament and denoted FIT.
, .
Since a team does not play itself, a natural property of a such a tournament is that strong teams get to play weaker teams, and weak teams play stronger teams.
This property is removed in equalized incomplete round robin tournaments .
enoted EIT.
, .
) where the sum of rankings of all opponents played is the same for each team.
Some results on fair incomplete round robin tournaments can be found in .
Still, we can design a tournament that may allow weak teams an even better chance at winning than an equalized incomplete tournament.
By allowing weak teams to play other weak teams, and having strong teams play other strong teams, the sequence w.
, w.
, .
, w.
should be an increasing arithmetic progression.
A tournament in which this condition is satisfied, and every team plays r < n Oe 1 games is called a handicap incomplete round robin tournament.
A summary of results of handicap tournaments obtained by the authors and other researchers can be found in .
In this paper we provide the details of the construction for n O 0 .
for all feasible Basic Notions By G = (V.
E) we mean a simple graph of order n.
We will identify vertex names with their labels, thus by stating i we refer to the vertex labeled i.
As previously mentioned, the study of handicap distance antimagic graphs was motivated by other tournament types, each of which had their own properties and associated graph labelings.
The graph of a fair incomplete round robin tournament admits a distance antimagic labeling, while the graph of an equalized incomplete round robin tournament admits a distance magic labeling.
The term distance magic labeling has evolved throughout the years.
The concept was originally coined as a sigma labeling by Vilfred .
in 1994, and then by Miller et.
using the name 1-vertex magic vertex labeling.
The definition of distance antimagic labeling nicely follows after the definition of distance magic labeling.
Definition 2.
A distance magic labeling of a graph G of order n is a bijection f : V Ie .
, 2, .
, .
with the property that there is a positive integer AA such that f .
= AA OAx OO V.
yOON .
The constant AA is called theP magic constant of the labeling f , and N .
denotes the set of all vertices adjacent to v.
The sum yOON .
is called the weight of vertex x and is denoted w.
A graph that admits a distance magic labeling is called a distance magic graph.
Definition 2.
A distance d-antimagic labeling of a graph G with n vertices is a bijection fA :
V Ie .
, 2, .
, .
with the property that there exists an ordering of the vertices of G such that the weights w.
1 ), w.
2 ), .
, w.
n ) forms an arithmetic progression with difference d.
When d = 1, then fA 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.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik A survey on distance magic graphs can be found in .
, while an often updated overview of results of all types of labelings can be found in .
The term handicap labeling was originally introduced by KovaArUovaA .
and previously referred to as ordered distance antimagic labeling by Froncek in .
Definition 2.
A handicap distance d-antimagic labeling of a graph G with n vertices is a bijection fI : V Ie .
, 2, .
, .
with the property that fI.
i ) = i and the sequence of the weights w.
1 ), w.
2 ), .
, w.
n ) forms an increasing arithmetic progression with difference d.
A graph G is a handicap distance d-antimagic graph if it allows a distance d-antimagic labeling, and a handicap distance antimagic graph when d = 1.
Note that in a handicap labeling a vertex with a lower label has a lower weight than a vertex with higher label.
Thus, if we think of the vertices as teams and label them according to their strength, an r-regular handicap distance antimagic graph is in fact a representation of a handicap incomplete round robin tournament.
Preliminary and Related Results We often seek to know for which pairs .
, .
does a fair, equalized, or handicap incomplete tournament exist.
The following results for fair and equalized incomplete tournaments with an even number of teams can be found in .
Theorem 3.
Let EIT.
, .
be an equalized incomplete complete tournament with n teams and r games per team.
Then r is even.
Theorem 3.
For n even an EIT.
, .
exists if and only if 2 O r O n Oe 2, r O 0 .
and either n O 0 .
or n O r 2 O 2 .
Theorem 3.
For n even a fair incomplete tournament FIT.
, .
exists if and only if 1 O k O n Oe 1, k O 1 .
and either n O 0 .
or n O k 1 O 2 .
For odd n, the following is known and obtained in .
Theorem 3.
Let n be an odd number and r = 2s q with s Ou 1 and q odd.
Then an EIT.
, .
exists whenever r O 72 .
Oe .
Theorem 3.
Let n be an odd number and k be an even number such that k < n and nOekOe1 6= 2z for any z > 0.
Then a fair incomplete tournament FIT.
, .
exists whenever k > 57 .
Oe .
Recently, some results on handicap distance d-antimagic graphs where d = 2 were obtained by the first author, including a full characterization for n O 0 .
Theorem 3.
If G is a k-regular 2-handicap graph, then k is even.
Theorem 3.
There exists a k-regular 2-handicap graph of order n for every positive n O 8 .
, n Ou 56 and every even k satisfying 6 O k O n Oe 50.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik Theorem 3.
There exists a k-regular 2-handicap graph of order n O 0 .
if and only if n Ou 16 and 4 O k O n Oe 6.
Even some results have been obtained for more general d-handicap tournaments by Freyberg in .
These include a variety of results for even d, a partial characterization of order n that permits d odd, and multiple restrictions on the feasible regularities based on n and d.
More details are known about handicap tournaments when d = 1, for the remainder of this paper this is the case.
For any graph with a given regularity r and order n a simple counting argument shows the weight of each vertex i is already known as in the following lemma .
Lemma 3.
In an r-regular handicap graph with n vertices the weight of every vertex is w.
= .
Oe .
/2 i.
Each vertex weight is an integer value obtained as a sum of integers.
The previous lemma is used in a number of non-existence results.
The following can be found amongst other nonexistence results, see e.
Lemma 3.
There exists no r-regular handicap graph with n vertices if both r and n are even.
Lemma 3.
No nontrivial r-regular handicap graph with n vertices exists if r = 1 and r = n Oe 1.
Lemma 3.
There is no .
Oe .
-regular handicap graph of order n.
We now proceed to the primary focus of this paper.
Construction for n O 0 .
If i is joined to k by an edge, we will use the notation .
Further, .
, .
c, .
will denote the complete bipartite graph where a and b are both adjacent to c and d and vice-versa.
The construction aims to prove the following proposition.
Proposition 4.
For n O 0 .
and r O 1, 3 .
, there exists an r-regular handicap graph G on n vertices for all feasible values of r, that is, 3 O r O n Oe 5.
First note that Lemmas 3.
2, 3.
3, and 3.
4 provide non-existence for all other r values than those claimed above.
Since r is odd and at least 3, we can partition the edges at each vertex as follows: 1 red edge, 2 blue edges, and 2s black edges for some nonnegative integer s.
In other words we will have a single 1-factor colored red, a pair of 1-factors that are colored blue, and 2s 1-factors with edges colored black.
The construction is complete in a three step process.
Step 1: The red edges will be used specifically to create the arithmetic progression required in the labeling by connecting .
, .
, .
, and .
This naturally partitions the vertex set intoAulowerAy and AuupperAy sets.
Let wr .
denote the weight of vertex i obtained from the red edges.
We have that wr .
= 4k i for i OO .
, 4.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik wr .
= Oe4k i for i OO .
k 1, 8.
Step 2: Now we construct the two blue edges to each vertex.
For the lower vertices, the blue edges will be copies of K2,2 as: .
, 4k.
, 4k Oe .
, .
, 4k Oe .
4, 4k Oe .
, .
, .
k Oe 1, 2k .
2k, 2k .
, and the upper vertices will be done in a similar manner: .
k 1, 8k.
k 2, 8k Oe .
, .
k 3, 8k Oe .
4k 4, 8k Oe .
, .
, .
k Oe 1, 6k .
6k, 6k .
See Figures 1 and 2.
Figure 1.
Lower blue edges.
Figure 2.
Upper blue edges.
Let wb .
denote the weight of vertex i obtained from the blue edges.
Then wb .
= 4k 1 for i OO .
, 4.
= 12k 1 for i OO .
k 1, 8.
so we have that wb .
= 4k 1 4k i = 8k 1 i for i OO .
, 4.
= 12k 1 Oe 4k i = 8k 1 i for i OO .
k 1, 8.
Thus the weight of each vertex with the red and blue edges is 8k 1 i for each i, which is exactly what we want.
The graph of red and blue edges is currently 3-regular and handicap.
All that is left is to show we can increase the regularity for any r O 1, 3 .
up to n Oe 5 as claimed in Proposition 4.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik Step 3: Our goal is to add 2s black edges such that the subgraph induced by the black edges is distance magic.
In doing so, we will not be effecting the arithmetic progression of our weights, and therefore, still have a handicap graph with higher regularities.
We need to be careful, though, to make sure that we are not trying to reuse any of the red or blue edges that are used in Steps 1 and To do this, we pair the vertices 1 with 8k, 2 with 8k Oe 1, .
, and 4k with 4k 1, so that the sum of these pairs is 8k 1.
Each of these pairs can be thought of as a graph H with no edges.
Each pair becomes a vertex in our bubble graph B.
In B, there will be an edge between two bubbles X = .
1 , x2 ) and Y = .
1 , y2 ) if and only if there would be a red or blue edge .
r bot.
between either x1 or x2 and y1 or y2 .
For clarity, we will color an edge red in B if it comes from Step 1.
Once all edges from Step 1 are accounted for, we then add the edges from Step 2 and of course color those blue.
While the colors in the bubble graph are not important, it helps to see where the edges came from.
What happens here is the red and blue edges create separate components of B, each of which is K4 .
To see this, take any bubble J = .
, 8k 1 Oe .
Since there is a red edge .
, we have [J|K] where K = .
k 1 Oe a, 4k .
We know the other half of the bubble K must have weight 4k 1 Oe a since the sum inside each bubble is 8k 1.
We also have the blue K2,2 involving a, namely .
, 4k 1 Oe .
a 1, 4k Oe .
Specifically, since there exists a blue edge .
, we have [J|L] where L = .
1, 8k Oe .
Similarly, [J|M ] where M = .
k Oe 1, 4k 1 .
Checking all other existing red and blue edges, we have a red edge .
k Oe a.
k Oe .
, and the blue K2,2 = .
k a, 8k 1 Oe a.
k 1 a, 8k Oe .
Observe that any red or blue edges that would emerge from the four bubbles J.
L, and M only result in edges between these four bubbles.
See Figure 3.
4k 1-a 8k 1-a 4k 1 a Figure 3.
Bubble structure.
Since we have n2 bubbles.
B = K n2 Oe n8 K4 .
This is in fact isomorphic to the complete multipartite graph K n8 .
, that is, a graph with n8 partite sets of size 4.
Observe the bubble graph B is 3-regular, and the complement B will be ( n2 Oe .
-regular.
B is the graph where we will pull our black edges from.
It is a well known result that the complete multipartite graph on an even number of vertices can be 1-factored .
Each black Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik edge in B will equate to a K2,2 in the blown up graph B[H], where B[H] is the lexicographic product of B and H.
Therefore, each 1-factor induced on B will consist of a 2-regular distance magic graph we can add to the red and blue edges, as desired.
If we use all available black edges, we can add 2( n2 Oe .
= n Oe 8 black edges to increase regularity, for a maximum regularity of n Oe 8 1 2 = n Oe 5.
Our construction is now complete, and we can state Proposition 4.
1 as a theorem.
Theorem 4.
For n O 0 .
and r odd, there exists an r-regular handicap graph G on n vertices if and only if 3 O r O n Oe 5.
Proof.
The necessity follows from Lemmas 3.
3 and 3.
For all feasible values of r, the existence follows from our construction above.
Example construction of 5-regular handicap graph on n = 32 vertices Since n = 32 = 8 A 4, we have in this example that k = 4.
Step 1: We start with the red edges by connecting .
, .
, and .
, since k = 4 we have .
, .
, .
, .
We obtain the following weights .
ee Figure .
= 4 A 4 i for i OO .
, .
ower vertice.
, wr .
= i Oe 4 A 4 for i OO .
, .
pper vertice.
Figure 4.
Step 1 on 32 vertices.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik Step 2: We now add the blue K2,2 Aos.
For the lower vertices: .
, 4k.
, 4k Oe .
, .
, 4k Oe .
4, 4k Oe .
, .
, .
k Oe 1, 2k .
2k, 2k .
, that is, .
, .
2, .
, .
, .
4, .
, .
, .
, .
8, .
Thus we are adding a weight of 17 to each lower vertex.
Upper vertices: .
k 1, 8k.
k 2, 8k Oe .
, .
k 3, 8k Oe .
4k 4, 8k Oe .
, .
, .
k Oe 1, 6k .
6k, 6k .
, that is, .
, .
18, .
, .
, .
, .
24, .
, adding a weight of 49 to each upper See Figure 5 .
otice the graph is not connecte.
We now have the following weights:
= 4 A 4 1 4 A 4 i for lower vertices and wb .
= 12 A 4 1 i Oe 4 A 4 for upper vertices.
Thus, we currently have a 3-regular handicap graph with w.
= 33 i for every i = 1, 2, .
, 32.
Figure 5.
Step 2 on 32 vertices.
Step 3: Now we take a look at which black edges are available to use.
First we construct the bubble graph B, drawing red or blue edges between bubbles for edges already used in step 1 or 2.
This is shown in Figure 6.
Figure 6 makes it more evident that B is a complete multipartite graph.
Let us refer to each bubble by the minimum of the two labels it contains.
Consider the bubbles 1, 2, 15, and 16.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik Figure 6.
Bubble graph and its complement on 32 vertices.
Regular handicap graphs of order n O 0 .
Froncek and A.
Shepanik In the complement, these will form one partite set, and each will have a black edge to bubbles 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, and 14.
Further, since 3, 4, 13, and 14 are all connected in B, these will form another partite set in B, and be joined to 1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 15, and 16.
continue in this fashion to see B is K4,4,4,4 , or K4.
B is shown in Figure 6.
Lastly we can choose our favorite 1-factor from a 1-factorization of B to increase regularity by two in our handicap graph.
No matter what we choose, we increase the weight of each vertex by 33 .
he sum of the vertices in each bubbl.
, resulting in a 5-regular handicap graph on 32 vertices with w.
= 66 i for all i.
Our final graph is shown in Figure 7.
Figure 7.
Step 3 on 32 vertices .
ncreasing regularit.
References