Plurality preference digraphs realized by trees—I. Necessary and sufficient conditions Original Research Article

In this paper we prove that an oriented graph D of order k is (n, n, k)-realizable by a tree of order n greater than k if and only if D is transitive and contains no induced anti-directed path of length 3 (i.e., D is series-parallel). We also derive some properties of an oriented graph D which is (n, n, n)-realizable by a tree and give a class of oriented graphs which are (n, n, n)-realizable by trees.