The Domination Graphs of Complete Paired Comparison Digraphs

Abstract

A complete paired comparison digraph $D$ is a directed graph in which $xy$ is an arc for all vertices $x,y$ in $D$, and to each arc we assign a real number $0\le a\le 1$ called a weight such that if $xy$ has weight $a$ then $yx$ has weight $1–a$. We say that two vertices $x,y$ dominate a third $z$ if the weights on $xz$ and $yz$ sum to at least $1$. If $x$ and $y$ dominate all other vertices in a complete paired comparison digraph, then we say they are a dominant pair. We construct the domination graph of a complete paired comparison digraph $D$ on the same vertices as $D$ with an edge between $x$ and $y$ if $x$ and $y$ form a dominant pair in $D$. In this paper, we characterize connected domination graphs of complete paired comparison digraphs. We also characterize the domination graphs of complete paired comparison digraphs with no arc weight of $.5$.