MEDIANS OF GRAPHS AND KINGS OF TOURNAMENTS
Hai-Yen Lee, Gerard J. Chang · 1997
We first prove that for any graph G with a positive vertex weight function w, there exists a graph H with a positive weight function w ′ such that w(v) = w ′ (v) for all vertices v in G and whose w ′-median is G. This is a generalization of a previous result for the case in which all weights are 1. The second result is that for any n-tournament T without transmitters, there exists an integer m ≤ 2n−1 and an m-tournament T ′ whose kings are exactly the vertices of T. This improves upon a previous result for m ≤ 2n.