×

On transitively orientable graphs. (English) Zbl 0586.05021

A graph G is transitively orientable if its edges can be oriented in such a way that an arc \(^{\to}\) exists whenever arcs of the form \(^{\to}\) and \(^{\to}\) exist. Two edges ab and cd of G are similar if there exists a path \((v_ 0,v_ 1,...,v_ m)\) where \(v_ 0=a\), \(v_ 1=b\), \(v_{m-1}=c\), and \(v_ m=d\) such that G contains no edge of the form \(v_ iv_{i+2}\) for \(0\leq i\leq m-2\). The authors deduce a recursive characterization of transitively orientable graphs that is formulated in terms of an equivalence class S of similar edges of G.
Reviewer: J.W.Moon

MSC:

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
PDFBibTeX XMLCite