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
    0 references

    Identifiers