\(P/d\)-Graphs of Tournaments

Abstract

Vertices \(x\) and \(y\) are called paired in tournament \(T\) if there exists a vertex \(z\) in the vertex set of \(T\) such that either \(x\) and \(y\) beat \(z\) or \(z\) beats \(x\) and \(y\). Vertices \(x\) and \(y\) are said to be distinguished in \(T\) if there exists a vertex \(z\) in \(T\) such that either \(x\) beats \(z\) and \(z\) beats \(y\), or \(y\) beats \(z\) and \(z\) beats \(x\). Two vertices are strictly paired (distinguished) in \(T\) if all vertices of \(T\) pair (distinguish) the two vertices in question. The \(p/d\)-graph of a tournament \(T\) is a graph which depicts strictly paired or strictly distinguished pairs of vertices in \(T\). \(P/d\)-graphs are useful in obtaining the characterization of such graphs as domination and domination-compliance graphs of tournaments. We shall see that \(p/d\)-graphs of tournaments have an interestingly limited structure as we characterize them in this paper. In so doing, we find a method of constructing a tournament with a given \(p/d\)-graph using adjacency matrices of tournaments.