Premium
Realization of digraphs by preferences based on distances in graphs
Author(s) -
Gu Weizhen,
Reid K. B.,
Schnyder Walter
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190309
Subject(s) - digraph , combinatorics , mathematics , graph , realization (probability) , upper and lower bounds , transitive relation , order (exchange) , quadratic equation , discrete mathematics , strongly connected component , preference relation , preference , mathematical analysis , statistics , geometry , finance , economics
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.