On edge transitivity of directed graphs (Q1894773)

From MaRDI portal





scientific article; zbMATH DE number 778538
Language Label Description Also known as
default for all languages
No label defined
    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
      0 references

      Identifiers