A Note on Handicap Incomplete Tournaments

摘要

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 (ⅰ) the total strength of the opponents that the stronger teams play with are higher, and (ⅱ) 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 rf-handicap labeling of a graph G = (V, E) on p vertices is a bijection l : V → {1, 2, …, p} with the property that l(v_i) = i and the sequence of weights w(v_1), w(v_2), …, w(v_p) forms an increasing arithmetic progression with difference rf, where w(v_i) = Σ_(v ∈ N(v_i))l(ⅴ). A graph G is d-handicap graph if it admits a rf-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 rf-handicap graphs for all k ≥ 1 and as an application, we characterize the rf-handicap labeling of Hamming graphs. Further, we give another method to construct EfT(p,r) from an infinite class of HIT(p,r) by increasing the number of rounds in HIT(p,r).