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