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 \leq a \leq 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\).