Physical Sciences and Mathematics Commons^™

Upset Paths And 2-Majority Tournaments, Rana Ali Alshaikh

Electronic Theses, Projects, and Dissertations

In 2005, Alon, et al. proved that tournaments arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B by at least two out of three voters, the tournament used to model this voting scenario has a minimum dominating set of size at most three. This result gives 2-majority tournaments some significance among all tournaments and motivates us to investigate when …