$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.