Geodesic
Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 2, pp. 429-435.

Voir la notice de l'article provenant de la source Library of Science

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ésar 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.
Keywords: graph orientation, 3-quasi-transitive digraph, 3-transitive digraph 
@article{DMGT_2013_33_2_a14,
     author = {Wang, Ruixia and Wang, Shiying},
     title = {Underlying {Graphs} of {3-Quasi-Transitive} {Digraphs} and {3-Transitive} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {429--435},
     publisher = {mathdoc},
     volume = {33},
     number = {2},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a14/}
}
TY  - JOUR
AU  - Wang, Ruixia
AU  - Wang, Shiying
TI  - Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 429
EP  - 435
VL  - 33
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a14/
LA  - en
ID  - DMGT_2013_33_2_a14
ER  - 
%0 Journal Article
%A Wang, Ruixia
%A Wang, Shiying
%T Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 429-435
%V 33
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a14/
%G en
%F DMGT_2013_33_2_a14
Wang, Ruixia; Wang, Shiying. Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 2, pp. 429-435. http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a14/

[1] J. Bang-Jensen, Kings in quasi-transitive digraphs, Discrete Math. 185 (1998) 19-27. doi:10.1016/S0012-365X(97)00179-9

[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000).

[3] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613

[4] A. Ghouila-Houri, Caractérization des graphes non orientés dont onpeut orienter les arrˆetes de mani`ere `aobtenir le graphe dune relation dordre, Comptes Rendus de l’Académie des Sciences Paris 254 (1962) 1370-1371.

[5] H. Galeana-Sánchez, I.A. Goldfeder and I. Urrutia, On the structure of strong 3- quasi-transitive digraphs, Discrete Math. 310 (2010) 2495-2498. doi:10.1016/j.disc.2010.06.008

[6] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in k-transitive and k-quasitransitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005

[7] S.Wang and R.Wang, Independent sets and non-augmentable paths in arc-locally insemicomplete digraphs and quasi-arc-transitive digraphs, Discrete Math. 311 (2011) 282-288. doi:10.1016/j.disc.2010.11.009