On edge transitivity of directed graphs (Q1894773)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On edge transitivity of directed graphs |
scientific article; zbMATH DE number 778538
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On edge transitivity of directed graphs |
scientific article; zbMATH DE number 778538 |
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