We obtained theoretical results for the development of methods for solving problems of linear ordering of objects based on labeled graphs. Solving the problem of planning of fair, equivalent and balanced (handicap) incomplete tournaments is equivalent to solving the problem of constructing of corresponding distance magic or antimagic labeling of an r -regular graph of order n . Let G (V , E) be distance magic graph, different from K1,2,2,...., 2 .We have proved the conjecture, which was presented by K. Sugeng, D.Froncek and others (K.A. Sugeng, D. Froncek, M. Miller, J. Ryan and J. Walker, On distance magic labeling of graphs, J. Combin. Math. Combin. Comput., 71 (2009), 39-48), that a set of vertices of the graph G can be partitioned into sets V1,V2 ,...,Vp , in such way that Vi 1 and G(Vi ) is the empty graph for every i 1, 2,...,p . We have also presented some results of edge and total vertex magic labeling of graphs/
The problem of linear ordering of objects is the mathematical model for many real life problems. There are different models of linear ordering, which include models of the ”sports” type. The main feature of this “sports” group is that its models use sum of points scored by the object as a ranking factor. Tournament models are widely used because of the simplicity of getting of the optimal solution. The quest for the optimal solution in planning of incomplete round-robin tournaments can be achieved with the help of methods of the graph labeling theory. In this paper, our main focus is on the properties of graphs with magic labeling, which can serve as models of incomplete round-robin tournaments. With a large number of competing teams, it is impossible to complete round-robin tournament in short period of time. Therefore, it is really necessary to have incomplete tournaments that imitate the complexity of a full round-robin tournament. There are several types of incomplete tournaments; each of them possesses its own, certain characteristics. Solving the problem of planning of fair, equivalent and balanced (handicap) incomplete tournaments for teams playing against opponents is equivalent to solving the problem of constructing of corresponding distance magic or anti-magic labeling of an r -regular graph of order n . The questions, regarding the existence of tournament graphs and methods of their construction, are very well described in works of D. Froncek, P. Kovar, T. Kovarova, A. Shepanik, M. Semeniuta.
Magic-type labelings are widely used in automated information systems. They come in handy
when one needs to calculate a check sum or to avoid using a lookup table. Simple graph may
represent a network of nodes and links with addresses (labels) intended for both links and nodes. If
the addresses form an edge magic labeling, it is enough to know the addresses of two vertices in order
to determine the address of their link without the lookup table, by simply subtracting the addresses
from the magic constant. The method for solving this problem is associated with a variety of
alternative solutions and requires the selection of optimal one; it also includes the process of linear
ordering of objects [
A. Rossa is considered to be the founder of the theory of labeling. He offered several types of
labeling as a tool for decomposing a complete graph into isomorphic subgraphs. Magic labeling was
first presented by D. Sedlyacek as a generalization of the concept of a magic square. D. Sedlyachek
called the edge labeling of graph as magical in case of backward numbers existence, as the label of
the edges of , with the following properties: (1) different vertices have different vertex labeles, and
(2) the sum of the values of the labels assigned to all edges incident to a given vertex is the same for
all vertices of graph . Details of edge-magic graphs can be found in the book ”Magic and Antimagic
Graphs” [
We consider only finite undirected graph without loops and multiple edges. We denote G (V , E) as a graph, where V is the set of vertices, and E is the set of edges. For the degree deg G (u) (or deg(u) ) of the vertex u of the graph G , the number of edges incident to u is equal. The maximum and minimum degrees of the vertices of the graph are denoted by the symbols (G) and (G) respectively.
If S is a finite set, then we denote S as its power. A set of subsets of a set S is called a partition S if the union of these subsets coincides with S and no two of them intersect.
Some graphs have certain names and designations. A graph of order n is called complete when each pair of its vertices is adjacent and it is denoted K n . Graph G (V , E) is considered to be k partition if we can represent V as a disjunctive union of sets V1,V2 ,...,Vk so that each edge of G connects only vertices from different sets. If each vertex Vi is adjacent to each vertex V j for any i, j 1, 2,...,k , i j and Vi V j ∅, then G is a complete k -partition graph, which we denote as Kn1 , Kn2 ,..., Knk , where Vi ni . If the graph is given by the set of vertices V {v1, v2 ,...,vn} and the set of edges E {(vk , vk1 | k 1,...,n 1} , then it is called a path of order n and is denoted P . A n cycle Cn of order n ( n 3 ) is a closed path. A graph is considered empty if the degrees of all its vertices are zero.
For any subset A V (G) of the set of vertices of a graph G (V , E) , the generated subgraph
G( A) is the maximum subgraph of the graph G with the set of vertices A . Two vertices with A are
adjacent in G( A) if and only if they are adjacent in G . A subset B V (G) is called a clique if the
subgraph G(B) generated by it is complete. The graph G(B) is also called a clique. A subset of the
vertices of a graph is called independent if the subgraph generated by it is empty. The terminology on
graph theory used in this article is presented in more detail in [
Distance magic labeling of graph G (V , E) of order p is a bijection f :V (G) {1, 2,..., p} , for which there exists an positive integer number k , such for every vertex u equality k f (v) is vN (u) fair, where N (u) is a set of vertices of graph G adjacent with u . Number k is called magic constant of labeling f , and a graph, which allows such labeling is distance magic.
Let us denote the theorems which used in the article.
Тhеоrem 1. [
Perfect matching M (or 1-factor) in a graph G is a 1-regular spanning subgraph of G .
Тhеоrem 2. [
Тhеоrem 3. If G (K p1 M ) K1 is a graph of odd order p with (G) p 1, where M is perfect matching in K p1 , then G K1,2,..., 2 .
Proof. Suppose, that G (K p1 M ) K1 is a graph of odd order p , where M is perfect matching in K p1 . Let u be a vertex of degree (G) p 1 in graph G , e.i. is adjacent with all vertices of G . Every vertex of G , different from u is not adjacent to only one vertex. Thus, G K1,2,..., 2 .
The Theorem has been proved.
Corollary 1. Graph K1,2,..., 2 is the distance magic graph.
The proof of the corollary follows directly from the theorems 2 and 3.
Example 1. Suppose G (K 6 M ) K1 (fig.1). Let us set vertex labeling of G , as it is shown in figure 1. The labeling is distance magic with magic constant k 21 . Let us identify the vertices with their labels. We divide the set of vertices V (G) into subsets {1, 6} , {2, 5}, {3, 4} , {7} . They are independent, moreover, these subsets are particles of the graph K1,2,2,2 such that G K1, 2, 2, 2 g is called total vertex-magic.
When planning sports competitions, when there is no possibility of holding a full round
tournament, the organizers of the competition put forward the following requirements: each team
must play with the same number of opponents; the complexity of the tournament for each team should
imitate the complexity of a full round robin tournament. To implement the second condition, n teams
are ranked, for example, based on the results of the previous year [9]. Teams can be evaluated in the
range from 1 to n , according to the occupied seats. Let’s identify the team number with its rank. The
strength of the i -th team in a full round tournament as understood as number sn (i) n 1 i , and
the total strength of the opponents of this team is the number S n, n1 (i) n(n 1) / 2 sn (i)
(n 1)(n 2) / 2 i. The sequence of all common strengths, arranged in ascending order, forms
an arithmetic progression with a difference of one. Therefore, to simulate a similar difficulty in an
incomplete round robin tournament, it is necessary to obtain an arithmetic progression from the total
strength of the opponents of each team. If such a tournament of n teams with r rounds, where
r n 1 arises from a round robin tournament by omitting certain matches, provided that each team
must play the same number of matches, it is denoted by FIT( , ) and is called a fair incomplete
tournament. In FIT( , ), each team plays with r other teams, and the total strength of opponents
playing with the i -th team is determinedby the formula Sr,n (i) (n 1)(n 2) / 2 i k for each i
and a fixed constant k . On the other hand, missed matches also form a kind of tournament, denoted
by EIT( , – –1) and called an equivalent incomplete tournament. In EIT( , – –1) each team plays
n r 1 matches and the total strength of the opponents Sr*,n (i) of the i -th team is the same and
equal to the constant k , i.e. Sr*,n (i) k . Obviously, FIT( , ) exists if and only if its complement
EIT( , – –1) exists. These tournaments have been studied in [
The mathematical model of the tournament can be a finite undirected graph that does not contain loops and multiple edges. Each team corresponds to the vertex of the graph and the two vertices are adjacent if a match has taken place between the respective teams. Since the rank of the command coincides with its number, the numbers from 1 to n are used as labels of the vertices of a graph of order n. Finding EIT( , ) is equivalent to solving the problem of the existence of remote magic labeling for an r -regular graph G of order n . In this regard, the paper considers the problem of finding the conditions for the existence of a distance magic labeling of a graph that is not isomorphic to the graph. Let us consider a system of p elements. The connections between its elements are assigned with numerical characteristics belonging to the set of natural numbers. Each element has a weight function equal to the sum of the numerical characteristics of the connections corresponding to this element. The system has the following properties: 1) different connections correspond to different natural numbers, 2) the weight function does not depend on the choice of the system element, i.e. It is a constant. It is necessary to choose from all variants of numerical characteristics of connections of the system the one for which weight function (constant) accepts the minimum from possible values. The mathematical model of this system is a magic graph with the least magical power of those magical labelings that it allows. Therefore, the actual problem is to determine the properties of graphs, which will make it possible to find the necessary and sufficient conditions for their magic.
Тhеоrem 4. If G (V , E) is a distance magic graph different from K1,2,..., 2 , then the set V of vertices can be partitioned into sets V1,V2 ,...,Vp in such way that Vi 1 and G(Vi ) is the empty graph for every i 1, 2,..., p .
Proof. According to the conditions G (V , E) is a graph other than K1,2,..., 2 , and G allows distance magic labeling f . Let G be a connected graph, in other case every component of the connectivity of this graph should be investigated in a similar way separately.
Any graph can be decomposed into subgraphs, each of which is a click or an empty graph. Therefore, we examine the graph G with the partition of the set of vertices V (G) on clicks and independent sets. Let V1,V2 ,...,Vp be the partitions, and V1 is a click of order n , and V2 ,V3,...,Vp are independent sets. In addition, we will assume that n is a minimum number for which there is a specified partition, otherwise the partition process can be continued.
Let denote the vertices G(Vi ) as {u1i , u2i ,...,uiV } and the degree of vertex uij in graph G as i degG (uij ) , where i 1, 2,..., p , j 1, 2,..., Vi .
If S is a sum of vertex labels in G(V1) and degG (ul1) degG (u1m ) n 1 , where ul1, u1m V1 , then we obtain the following weights for these vertices: wG (ul1) s f (ul1) and wG (u1m ) s f (u1m ) . Here we have f (ul1) f (u1m ) . Thus, the degrees in a graph G less than n 1 of vertices from set {u1i , u2i ,...,uiV } must exceed n 1 , otherwise the condition of being magic is violated. But in this case i you can get a new partition into V (G) subsets, each of which is empty. Similar considerations can be performed if there is more than one click in the partition.
Suppose, that among V1,V2 ,...,Vp , there are at least two sets of power one, for example, | V1 V2 1. Then vertices u1i Vi ( i 1, 2 ) must be adjacent to every vertex of the corresponding set V Vi in graph G . According to theorem 1, the graph G is not distance magic. We came to a contradiction with the condition of the theorem 4.
If there is only one set Vi from Vi 1 , then its only vertex u1i Vi is adjacent to every vertex of the set V Vi in graph G . According to theorems 2 and 3, and the corollary 1, we get G K1,2,..., 2 , which contradicts the condition of the theorem 4. The theorem has been proved.
Corollary 2. Let G (V , E) be a distance magic r -regular graph of order n . Then for the power of any independent set Vi in G double inequality 1 Vi
n r is fair, where is the minimum eigenvalue of the adjacency matrix .
The proof of the corollary 2 follows directly from theorem 4 and the known Delsart-Hoffmann results with respect to the upper limit on the power of the independent set.
When we use distance magic graphs as mathematical models to solve specific practical problems,
then attention should be paid to the fact that the magic constant takes the only value for any distance
magic graph [
Let G (V , E) be a graph with p vertices and q edges, i.e. the ( p, g ) graph with edge labeling . Let numbers x1 ,...xq form a set of edge labels of G . We denote the vertices of G as u1 , u2 ,...u p . It is obvious, G is the magic graph with magic constant if and only if, the system * (ui ) (i 1,2,..., p) . of p linear equations with q 1 unknowns x1 ,...xq , , has a solution on the set of positive integer numbers. If this system has no solution, it means that the graph is not magic. If there exists such a solution, then it corresponds to the magical labeling of the graph G . In this case, there is an unlimited family of magical labelings if this graph, and among them there is one that will give the value (G) . The matrix record the system of linear equation has the form where A(G) is the incidence matrix of graph G , X T (x1, x2 ,..., xq ), I – column-matrix with p rows, all elements of which equal one.
Example 2. Determine the magical power of the graph G , shown in figure 2. We set the edge labeling of the graph G , as it is shown in figure 2. Suppose, that G is magic with magic constant . Then the system of linear equations for the graph looks like * (ui ) , where i 1,2,..., p or x1 x2 , x4 x5 , x7 x8 , x1 x3 x8 x9 , x2 x3 x4 x6 , x5 x6 x7 x9 .
After performing elementary transformations on the equations of the system, we obtain the following equation x3 x6 x9 0 . Therefore, the system on the set of positive integer numbers has no solution. We came to a contradiction with the assumption. Thus, the graph G has no magical labeling, so its magical power is zero.
The method of finding the magic labeling of a graph, and hence its magical power using a system of linear equations is not effective, especially for graphs of large orders. Therefore, it is advisable to obtain the properties of graphs that allow you to set the necessary and/or sufficient conditions of being magic. For example, a magic graph cannot contain more than one edge with a ended vertex of degree one, and it can not contain edges with ended vertices of degree two. It follows that a 1-regular graph will be magical if and only if it is isomorphic of K 2 and there are no 2-regular magic graphs.
Representatives of class M (0) are all graphs containing a path of the form deg( y) deg( z) 2. Here are examples of such graphs. xyzt with
Consider two connected graphs G1 and G2 , that have no common elements. Randomly select one vertex in each column and connect them with a path Pk , each inner vertex of which does not belong to any of the graphs G1 , G2 . The graph is denoted as G1 : Pk : G2 . Graph G1 : Pk : G2 .does not allows magic labeling where k 4 , and graph Gm : Pp : Gn does not allow magic labeling where 3 m n for any k .
Let G1, G2 ,...,Gk (k 2) be connected graphs, and ui V (Gi ) is a randomly selected vertex. Then the graph, obtained conneсting edge of vertex ui of graph Gi with corresponding vertex ui1 of graph Gi1 for i 1,2,..., k 1 is called path connection of graph G1, G2 ,..., Gk . Path connection of an arbitrary number of cycles is not a magic graph.
The relations between the magic constant and the degrees of the vertices of the graph are presented in the following lemmas.
Lemma 1. If graph G allows magic labeling with magic constant , then
Proof. Weight of vertex of maximum degree of graph G is a sum of edge labels, each of which is not less than one 1. Тhen (G). The equal sign is possible only for the graph K 2 .
On the other hand, to the vertex of the last degree (G) labels are incidental, which give the sum of . Amoung them there is a label which not less that (G) . Thus, (G) (G) .
Corollary 3. If G is a magic graph, then (G) (G) .
Lemma 2. Let G be a graph of order p, which allows magic labeling with magic constant . Then the number p is even. Proof. Suppose, that the graph G of order p allows magic labeling with magic constant . We denote the sum of all edges of graph G as S . Every vertex from p has a weight , then product p represents twice the amount of labels. Thus, p 2S.
Lemma has been proved.
Corollary 4. If graph G of odd order allows magic labeling with magic constant , then 0(mod 2) . In some cases, it is convenient to consider as mathematical models those graphs which have total labeling that satisfy certain properties. Let us dwell on the study of regular graphs with such labelings
For r regular graph G (V , E) of order p and size q with total vertex-magic labeling g and magic constant k there is dual labeling g' , defined as follows g' (u) p q 1 g(u) and g' (uv) p q 1 g(uv) for any u V , uv E. We denote magic constant for g' as k' , then k ' k (r 1).
The graph G x (V x, E* ), where x E(G) is obtained from the graph G (V , E) adding a vertex and all edges, which are connecting the vertex to all vertices of set V (G).
Let G be a regular graph of order p and size q with total vertex labeling g and. For the graph G x we consider such a total labeling g * , that g * (ui ) g(ui ), g * (uiu j ) g(uiu j ), g * (x) 2 p g 1, for g * (ui x) p g i, any ui V (G), ui v j E(G), where i j,i, j 1,2,..., p. We obtain the following weights for the vertices of graph G x : wt (ui ) k p g i, wt (x) 1 3 p 2 5 p q( p 1) 1. . As we can see, the weights 2 of vertices ui in graph G x at different values i are different. If we suppose, that there is i 1,2,..., p at which wt (ui ) wt (x) , then we obtain k i 2 p( p 1) pq 1. . This is 3 impossible since k i const. In this case, the labeling g * is called total vertex-antimagic.
We have proved the following theorem. Тhеоrem 5. If G is a regular total vertex-magic graph, then G x allows total vertex antimagic labeling. It is easy to establish the relationship between the magical and total vertex-antimagic labelings of 2-regular graphs.
Тhеоrem 6. Let G be a 2-regular magic graph of order p and size q with a set of edge labeles {1, 2, , p} . Then G allows total vertex-antimagic labeling.
Proof. Let be a magic labeling of 2-regular graph G of order p and size q , whith a set of edge labels {1, 2, , q}, and is his magic constant and V u1 , u2 ,..., u p V {u1, u2 , , u p}. We denote total labeling g * of graph G as the following: g* (uiu j ) (uiu j ) , g * (ui ) q i for any ui V (G), ui v j E(G), where i j,i, j 1,2,..., p. Let’s calculate the weights of the vertices for labeling g * : wt (ui ) q i. They are all different, therefore, g * is total vertexantimagic labeling. The theorem has been proved.
In the course of the study, we obtained a proof of the hypothesis presented by K.Sugeng,
D. Froncek and others in [