Realization of digraphs by preferences based on distances in graphs

Consider a graph G with two distinguished sets of vertices: the voters and the candidates. A voter v prefers candidate x to candidate y if d(v, x) < d(v, y). This preference relation defines an asymmetric digraph whose vertices are the candidates, in which there is an arc from candidate x to candidate y if and only if more voters prefer x to y than prefer y to x. T. W. Johnson and P. J. Slater (“Realization of Majority Preference Digraphs by Graphically Determined Voting Patterns,” Congressus Numerantium , vol. 67 [1988] 175‐186) have shown that each asymmetric digraph of order n can be realized in this way using a graph of order O( n 2 ). We present a new construction reducing the quadratic upper bound to a linear bound. © 1995 John Wiley & Sons, Inc.