Geodesic
Some Results on 4-Transitive Digraphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 117-129.

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

Let D be a digraph with set of vertices V and set of arcs A. We say that D is k-transitive if for every pair of vertices u, v ∈ V, the existence of a uv-path of length k in D implies that (u, v) ∈ A. A 2-transitive digraph is a transitive digraph in the usual sense. A subset N of V is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V. The problem of determining whether a digraph has a k-kernel is known to be NP-complete for every k ≥ 2. In this work, we characterize 4-transitive digraphs having a 3-kernel and also 4-transitive digraphs having a 2-kernel. Using the latter result, a proof of the Laborde-Payan-Xuong conjecture for 4-transitive digraphs is given. This conjecture establishes that for every digraph D, an independent set can be found such that it intersects every longest path in D. Also, Seymour’s Second Neighborhood Conjecture is verified for 4-transitive digraphs and further problems are proposed.
Keywords: 4-transitive digraph, k -transitive digraph, 3-kernel, k -kernel, Laborde-Payan-Xuong Conjecture 
@article{DMGT_2017_37_1_a8,
     author = {Garc{\'\i}a-V\'azquez, Patricio Ricardo and Hern\'andez-Cruz, C\'esar},
     title = {Some {Results} on {4-Transitive} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {117--129},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a8/}
}
TY  - JOUR
AU  - García-Vázquez, Patricio Ricardo
AU  - Hernández-Cruz, César
TI  - Some Results on 4-Transitive Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 117
EP  - 129
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a8/
LA  - en
ID  - DMGT_2017_37_1_a8
ER  - 
%0 Journal Article
%A García-Vázquez, Patricio Ricardo
%A Hernández-Cruz, César
%T Some Results on 4-Transitive Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 117-129
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a8/
%G en
%F DMGT_2017_37_1_a8
García-Vázquez, Patricio Ricardo; Hernández-Cruz, César. Some Results on 4-Transitive Digraphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 117-129. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a8/

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

[2] V. Chvátal, On the computational complexity of finding a kernel, Technical Report Centre de Recherches Mathématiques, Université de Montréal CRM-300 (1973).

[3] H. Galeana-Sánchez and R. Gómez, Independent sets and non-augmentable paths in generalizations of tournaments, Discrete Math. 308 (2008) 2460–2472. doi:10.1016/j.disc.2007.05.016

[4] H. Galeana-Sánchez, R. Gómez and J.J. Montellano-Ballesteros, Independent transversals of longest paths in locally semicomplete and locally transitive digraphs, Discuss. Math. Graph Theory 29 (2009) 469–480. doi:10.7151/dmgt.1458

[5] H. Galeana-Sánchez and C. Hernández-Cruz, On the existence of ( k, l ) -kernels in digraphs with a given circumference, AKCE Int. J. Graphs Comb. 10 (2013) 15–28.

[6] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in generalizations of transitive digraphs, Discuss. Math. Graph Theory 31 (2011) 293–312. doi:10.7151/dmgt.1546

[7] H. Galeana-Sánchez and C. Hernández-Cruz, On the existence of ( k, l ) -kernels in infinite digraphs: A survey, Discuss. Math. Graph Theory 34 (2011) 431–466. doi:10.7151/dmgt.1747

[8] H. Galeana-Sánchez and C. Hernández-Cruz, Cyclically k-partite digraphs and k-kernels, Discuss. Math. Graph Theory 31 (2011) 63–79. doi:10.7151/dmgt.1530

[9] 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

[10] P. Hell and C. Hernández-Cruz, On the complexity of the 3 -kernel problem in some classes of digraphs, Discuss. Math. Graph Theory 34 (2014) 167–186. doi:10.7151/dmgt.1727

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

[12] 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

[13] C. Hernández-Cruz and J.J. Montellano-Ballesteros, Some remarks on the structure of strong k-transitive digraphs, Discuss. Math. Graph Theory 34 (2015) 651–672. doi:10.7151/dmgt.1765

[14] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest paths in digraphs, Graphs and Other Combinatorial Topics, Proceedings of the Third Czechoslovak Symposium of Graph Theory (1982) 173–177.

[15] R. Wang, ( k − 1) -kernels in strong k-transitive digraphs, Discuss. Math. Graph Theory 35 (2015) 229–235. doi:10.7151/dmgt.1787

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