## A Note on Handicap Incomplete Tour- naments

Publication Type : Book Chapter

Publisher : Springer

Source : In: Colbourn C., Grossi R., Pisanti N. (eds) Combinatorial Algorithms. IWOCA 2019, Italy. Lecture Notes in Computer Science, 11638. 1-9, Springer Cham, 2019

Campus : Amritapuri

School : School of Arts and Sciences

Department : Mathematics

Year : 2019

Abstract : An equalized incomplete tournament EIT(p, r) on p teams which are ranked from 1 to p, is a tournament in which every team plays against r teams and the total strength of the opponents that every team plays with is a constant. A handicap incomplete tournament HIT(p, r) on p teams is a tournament in which every team plays against r opponents in such a way that (i) the total strength of the opponents that the stronger teams play with are higher, and (ii) the total strength of the opponents that the weaker teams play with are lower. Thus, every team has an equal chance of winning in a HIT(p, r). A d-handicap labeling of a graph G=(V,E) on p vertices is a bijection l:V→{1,2,⋅⋅⋅,p} with the property that l(vi)=i and the sequence of weights w(v1),w(v2),⋅⋅⋅,w(vp) forms an increasing arithmetic progression with difference d, where w(vi)=∑v∈N(vi)l(v). A graph G is d-handicap graph if it admits a d-handicap labeling. Thus, existence of an r-regular d-handicap graph guarantees the existence of a HIT(p, r). In this paper, we give a method to construct new (d+k)-handicap graphs from d-handicap graphs for all k≥1 and as an application, we characterize the d-handicap labeling of Hamming graphs. Further, we give another method to construct EIT(p, r) from an infinite class of HIT(p, r) by increasing the number of rounds in HIT(p, r).

Cite this Research Publication : A V Prajeesh, K Paramasivam, N Kamatchi, A Note on Handicap Incomplete Tour- naments. In: Colbourn C., Grossi R., Pisanti N. (eds) Combinatorial Algorithms. IWOCA 2019, Italy. Lecture Notes in Computer Science, 11638. 1-9, Springer Cham, 2019. https://doi.org/10.1007/978-3-030-25005-8 1