On edge transitivity of directed graphs

DOI10.1016/0012-365X(93)E0182-4MaRDI QIDQ1894773zbMATH OpenFDO

Authors Jayme L. Szwarcfiter

Publication date 9 November 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)E0182-4

zbMATH Keywords

acyclic orientationcharacterizationcircle graphsdimensiondirected graphsedge transitivityinterval graphlocal comparability graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

• On transitive orientations of G-e
• scientific article; zbMATH DE number 3939387
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• scientific article; zbMATH DE number 3847443
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'

Cites work

• Betweenness, orders and interval graphs
• Complexity of diagrams
• Dimension transitiv orientierbarer graphen
• scientific article; zbMATH DE number 19214 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3588700 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• On cliques in graphs
• Orientations of circle graphs
• Recognizing circle graphs in polynomial time
• Reconnaissance des graphes de cordes
• Reducing prime graphs and recognizing circle graphs
• The Complexity of Enumeration and Reliability Problems
• The Complexity of the Partial Order Dimension Problem
• The Dimension of a Comparability Graph

Cited in

(4)

• scientific article; zbMATH DE number 3939387 (Why is no real title available?)
• scientific article; zbMATH DE number 15035 (Why is no real title available?)
• The independent compatible edges topology of directed graphs
• scientific article; zbMATH DE number 5237243 (Why is no real title available?)

This page was built for publication: On edge transitivity of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894773)