Open AccessUnderlying graphs of 3-quasi-transitive digraphs and 3-transitive digraphs
Author(s) -
Shiying Wang,
Ruixia Wang
Publication year - 2013
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1680
Subject(s) - transitive relation , digraph , combinatorics , mathematics , conjecture , transitive reduction , graph , discrete mathematics , line graph , voltage graph
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). Ćesar Hernández-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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom