On edge transitivity of directed graphs (Q1894773)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On edge transitivity of directed graphs |
scientific article |
Statements
On edge transitivity of directed graphs (English)
0 references
9 November 1995
0 references
The author calls a graph \(G\) a local comparability graph if its edges can be given an acyclic orientation such that for each arc \(uv\), the subgraph induced by the nodes that are simultaneously ancestors of \(v\) and descendants of \(u\) is transitive. He then defines a parameter called the dimension of the graph and shows that a local comparability graph has dimension one if and only if it is a connected proper interval graph. He also gives a new characterization of circle graphs in terms of edge transitivity.
0 references
directed graphs
0 references
local comparability graph
0 references
acyclic orientation
0 references
dimension
0 references
interval graph
0 references
characterization
0 references
circle graphs
0 references
edge transitivity
0 references