Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-01-27T19:32:45.423Z Has data issue: false hasContentIssue false
  • English
  • Français

Transitive Orientation of Graphs and Identification of Permutation Graphs

Published online by Cambridge University Press:  20 November 2018

A. Pnueli ,
A. Lempel  and
S. Even
A. Pnueli
Affiliation:
The Weizmann Institute of Science, Rehovot, Israel
A. Lempel
Affiliation:
Sperry Rand Research Center, Sudbury, Massachusetts
S. Even
Affiliation:
Sperry Rand Research Center, Sudbury, Massachusetts
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 G or (V, E), where V is the set of vertices and E is the set of edges. An edge joining the vertices i,j ∊ V will be denoted by the unordered pair (i,j).

An orientation of G = (V, E) is an assignment of a unique direction i → j or j → i to every edge (i,j) ∊ E. The resulting directed image of G will be denoted by G→ or (V, E→), where E→ is now a set of ordered pairs E→ = {[i,j]| (i,j) ∊ E and i → j}. Notice the difference in notation (brackets versus parentheses) for ordered and unordered pairs.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 23 , Issue 1 , February 1971 , pp. 160 - 175
Copyright
Copyright © Canadian Mathematical Society 1971

References

1. Even, S., Lempel, A., and Pnueli, A., Permutation graphs and transitive graphs, Sperry Rand Research Center Report No. SRRC-RR-70-11, February 1970, ACM J. (to appear).Google Scholar
2. Gilmore, P. C. and Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Can. J. Math. 16 (1964), 539–548.Google Scholar
3. Knuth, D. E., The art of computer programming, Vol. 1: Fundamental algorithms, §2.2.2 (Addison-Wesley, Reading, Massachusetts, 1968).Google Scholar
4. Liu, C. L., Introduction to combinatorial mathematics, Chapter 9, Example 9-5 (McGraw-Hill, New York, 1968).Google Scholar