Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs

Abstract

A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). C´esar Hern´andez-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation. In this paper, we shall prove that the conjecture is true.

Keywords

• graph orientation
• 3-quasi-transitive digraph
• 3-transitive digraph