Transitive Orientation of Graphs and Identification of Permutation Graphs

<jats:p>The graphs considered in this paper are assumed to be finite, with no edge joining a vertex to itself and with no two distinct edges joining the same pair of vertices. An undirected graph will be denoted by <jats:italic>G</jats:italic> or (<jats:italic>V, E</jats:italic>), where <jats:italic>V</jats:italic> is the set of vertices and <jats:italic>E</jats:italic> is the set of edges. An edge joining the vertices <jats:italic>i,j</jats:italic> ∊ <jats:italic>V</jats:italic> will be denoted by the unordered pair (<jats:italic>i,j</jats:italic>).</jats:p><jats:p>An <jats:italic>orientation</jats:italic> of <jats:italic>G</jats:italic> = (<jats:italic>V, E</jats:italic>) is an assignment of a unique direction <jats:italic>i</jats:italic> → <jats:italic>j</jats:italic> or <jats:italic>j</jats:italic> → <jats:italic>i</jats:italic> to every edge (<jats:italic>i,j</jats:italic>) ∊ <jats:italic>E</jats:italic>. The resulting directed image of <jats:italic>G</jats:italic> will be denoted by <jats:italic>G<jats:sup>→</jats:sup></jats:italic> or (<jats:italic>V</jats:italic>, <jats:italic>E→</jats:italic>), where <jats:italic>E→</jats:italic> is now a set of ordered pairs <jats:italic>E→</jats:italic> = {[<jats:italic>i,j</jats:italic>]| (<jats:italic>i,j</jats:italic>) ∊ <jats:italic>E</jats:italic> and <jats:italic>i</jats:italic> → <jats:italic>j</jats:italic>}. Notice the difference in notation (brackets versus parentheses) for ordered and unordered pairs.</jats:p>