Affordable Access

Publisher Website

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

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
147
Identifiers
DOI: 10.1016/0012-365x(94)00165-f

Abstract

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

There are no comments yet on this publication. Be the first to share your thoughts.