Geodesic
Some remarks on the structure of strong $k$-transitive digraphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 4, pp. 651-671.

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

A digraph D is k-transitive if the existence of a directed path (v_0, v_1, . . ., v_k), of length k implies that (v_0, v_k) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.
Keywords: digraph, transitive digraph, k-transitive digraph, quasi-transitive digraph, k-quasi-transitive digraph, Laborde-Payan-Xuong Conjecture 
@article{DMGT_2014_34_4_a0,
     author = {Hern\'andez-Cruz, C\'esar and Montellano-Ballesteros, Juan Jos\'e},
     title = {Some remarks on the structure of strong $k$-transitive digraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {651--671},
     publisher = {mathdoc},
     volume = {34},
     number = {4},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a0/}
}
TY  - JOUR
AU  - Hernández-Cruz, César
AU  - Montellano-Ballesteros, Juan José
TI  - Some remarks on the structure of strong $k$-transitive digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 651
EP  - 671
VL  - 34
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a0/
LA  - en
ID  - DMGT_2014_34_4_a0
ER  - 
%0 Journal Article
%A Hernández-Cruz, César
%A Montellano-Ballesteros, Juan José
%T Some remarks on the structure of strong $k$-transitive digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 651-671
%V 34
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a0/
%G en
%F DMGT_2014_34_4_a0
Hernández-Cruz, César; Montellano-Ballesteros, Juan José. Some remarks on the structure of strong $k$-transitive digraphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 4, pp. 651-671. http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a0/

[1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag Berlin, Heidelberg New York, 2002).

[2] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag Berlin, Heidelberg New York, 2005).

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

[4] A. Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienterles arrêtes de manière à obtenir le graphe d’une relation d’ordre, C. R. Acad. Sci. Paris 254 (1962) 1370-1371.

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

[6] C. Hernández-Cruz, 4-transitive digraphs I: The structure of strong 4-transitive digraphs, Discuss. Math. Graph Theory 33 (2013) 247-260. doi:10.7151/dmgt.1645

[7] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other Combinatorial Topics, Prague, M. Fiedler (Ed(s)), (Teubner, Leipzig, 1983) 173-177.

[8] R. Wang, A conjecture on k-transitive digraphs, Discrete Math. 312 (2012) 1458-1460. doi:0.1016/j.disc.2012.01.011

[9] R. Wang and S. Wang, Underlying graphs of 3-quasi-transitive digraphs and 3- transitive digraphs, Discuss. Math. Graph Theory 33 (2013) 429-436. doi:10.7151/dmgt.1680