Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2018.05.013

Upr. sist. maš., 2018, Issue 5 (277), pp. 13-24.

UDC 519.1

Semeniuta Marina F., PhD in Phys.-Math. Sciences, professor Department of Physics and Mathematics Sciences of the Flight Academy of the National Aviation University, st. Dobrovolsky, 1, Kropivnitsky, 25005, Ukraine, marina_semenyuta@ukr.net

Sherman Zoya A., PhD in Phys.-Math. Sciences, senior lecturer, Department of Medical physics and information technology №2 of Donetsk National Medical University, st. Pryvokzalnaya, 27, Liman, 84404, Donetsk region, Ukraine,
E-mail: sherman.zoya@gmail.com

Dmitriiev Oleh M., PhD, head of the department of flight operations, aerodynamics and flight dynamics of the Flight Academy of the National Aviation University, E-mail – Dmitronik70@i.ua

Incomplete tournaments and magic types of labeling

Introduction. There is a variety of types of sports tournaments whose planning is based on the construction of graph models. Each type of tournament has its own characteristics. In this paper, fair, equitable and balanced partial competitions are considered. Creating a tournament grid for n teams playing with r opponents for such tournaments is equivalent to solving the problem of constructing an appropriate distant magic or antimagic labeling of the r-regular graph of order n.

Purpose. The purpose of the article is to systematize the main theoretical information related to this topic, to highlight the problems that have not been solved, to classify the methods of constructing graphs of tournaments and to unify the algorithms for their description in accordance with this classification.

Methods. New algorithms for constructing incomplete tournaments graphs are offered. This makes it possible to extend the range of tasks using mathematical models based on labeled graphs.

Results. All methods of constructing graphs of tournaments are divided into three groups. The methods of the first group included those based on the properties of magic rectangles, including Kotsih arrays. Methods of the second and third groups are constructive and contain elements of induction. Each group is related to the definition of a particular factor or factorization of the graph, which is involved in building a graph of the tournament.

Conclusion. In the process of analyzing the theoretical advances of the studied problem the systematization of the existing results has been made. All methods for constructing incomplete tournament graphs are divided into three groups. New approaches for their realization are offered. This makes it possible to extend the range of tasks using mathematical models based on labeled graphs.

Download full text! (In Russian).

Keywords: fair incomplete tournament, equalized incomplete tournament, handicap tournament, distance magic labeling, d-antimagic distance labeling, d-handicap distance antimagic labeling.

1. Sugeng, K.A., Froncek, D., Miller, M., Ryan, J., Walker, J., 2009. “On distance magic labeling of graphs”, Journal of Combinatorial Mathematics and Combinatorial Computing, 71, pp. 39-48.
2. Vilfred, V., 1994. Sigma labelled graphs and circulant graphs. Ph.D. Thesis, University of Kerala, India.
3. Miller, M., Rodger, C., Simanjuntak, R., 2003. “Distance magic labelings of graphs”. Australasian Journal of Combinatorics, 28, pp. 305-315.
4. Arumugam, S., Froncek, D., Kamatchi, N., 2011. “Distance magic graphs – a survey”. Journal of the Indonesian Mathematical Society. Special Edition, pp. 11-26.
5. Gallian, J.A.A., 2017. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics, DS6: Dec 22, 432 p.
6. Arumugam, S., Kamatchi, N., 2012. “On (a; d)-distance antimagic graphs”. Australasian journal of combinatorics, 54, pp. 279-287.
7. Froncek, D., 2013. “Handicap distance antimagic graphs and incomplete tournaments”. AKCE International Journal of Graphs and Combinatorics, 10 (2), pp. 119-127.
8. Kamatchi, N., Ramalakshmi, A., Nilavarasi, S, Arumugam, S., 2015. “A note on distance magic and distance antimagic”. Electronic Notes in Discrete Mathematics, 48, pp. 183-187.
   https://doi.org/10.1016/j.endm.2015.05.027
9. Nalliah, M., 2014. Antimagic labelings of graphs and digraphs: Ph. D. thesis. M.Nalliah. The National Centre for Advanced Research in Discrete Mathematics, University of Kalasalingam.
10. Semeniuta, M., 2016. “On distance antimagic labeling of graphs”. Collection of Scientific Works of V.M. Glushkov Institute of Cybernetics of NAS of Ukraine “The Theory of Optimal Solutions”, pp. 26- 32.
11. Semeniuta, M., 2016. “(a,d)-distance antimagic labeling of certain types of graphs”. Cybernetics and Systems Analysis, 52 (6), pp. 135 – 142.
    https://doi.org/10.1007/s10559-016-9897-z
12. Semeniuta, M., 2018. “On (a,d)-distance antimagic and 1-vertex bimagic vertex labeling of certain types of graphs”. Cybernetics and Systems Analysis, 54 (2), pp. 134-141.
    https://doi.org/10.1007/s10559-018-0031-2
13. Froncek, D., Kovar, P., Kovarova, T., 2006. “Fair incomplete tournaments”. Bull. Inst. Combin. Appl., 48, pp. 31-33.
14. Froncek, D., 2007. “Fair incomplete tournaments with odd number of teams and large number of games”. Congr. Numer., 187, pp. 83-89.
15. Shepanik, A., 2015. Graph labelings and tournament scheduling. MS Thesis. University of Minnesota Duluth, 55 p.
16. Froncek, D., Shepanik, A., 2016. “Regular handicap tournaments of high degree”. Journal of Algebra Combinatorics Discrete Structures and Applications, 3 (3), pp. 159-164.
    https://doi.org/10.13069/jacodesmath.22530
17. Kovar, P., Kravcenko, M., Krbecek, M., Silber, A., 2017. “Handicap labelings of 4-regular graphs”. Discrete mathematics, 15 (2), pp. 331-335.
18. Froncek, D., 2017. “A note on incomplete regular tournaments with handicap two of order nº0(mod8)”. Opuscula Math., 37 (4), pp. 557-566.
    https://doi.org/10.7494/OpMath.2017.37.4.557
19. Froncek, D., Kovar, P., Kovarova, T., Krajc, B., Kravcenko, M., Shepanik, A., Silber, A., 2017. “On regular handicap graphs of oven order”. Electronic Notes in Discrete Mathematics, 60, pp. 69-76.
    https://doi.org/10.1016/j.endm.2017.06.010
20. Froncek, D., Shepanik, A., 2018. “Regular handicap graph of order nº0(mod8)”. Electronic Journal of Graph Theory and Applications, 6 (2), pp. 208-218.
    https://doi.org/10.5614/ejgta.2018.6.2.1
21. Freyberg, B., 2017. Distance magic type and distance anti-magic-type labelings of Graphs. Ph.D.Thesis. Michigan Technological University, Michigan, USA, 150 p.
22. Harari, F., 1973. Graph Theory. M.: Peace, 300 p.
23. Semeniuta, M., 2008. Investigation of timetables and numbering graphs: candidate thesis of physical and mathematical sciences: 01.01.08. K., 190 p.

Received  21.11.18