DMGT

Discussiones Mathematicae Graph Theory 33(2) (2013) 247-260
DOI: https://doi.org/10.7151/dmgt.1645

4-transitive Digraphs I: The Structure of Strong 4-transitive Digraphs

César Hernández-Cruz

Instituto de Matemáticas
Universidad Nacional Autónoma de México
Ciudad Universitaria, México, D.F., C.P. 04510, México

Abstract

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v, w ∈ V(D), (u,v), (v,w) ∈ A(D) implies that (u,w) ∈ A(D). This concept can be generalized as follows: A digraph is k-transitive if for every u,v ∈ V(D), the existence of a uv-directed path of length k in D implies that (u,v) ∈ A(D). A very useful structural characterization of transitive digraphs has been known for a long time, and recently, 3-transitive digraphs have been characterized.

In this work, some general structural results are proved for k-transitive digraphs with arbitrary k ≥ 2. Some of this results are used to characterize the family of 4-transitive digraphs. Also some of the general results remain valid for k-quasi-transitive digraphs considering an additional hypothesis. A conjecture on a structural property of k-transitive digraphs is proposed.

Keywords: digraph, transitive digraph, quasi-transitive digraph, 4-transitive digraph, k-transitive digraph, k-quasi-transitive digraph

2010 Mathematics Subject Classification: 05C20, 05C75.

References

[1]	J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag, Berlin Heidelberg New York, 2002).
[2]	J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141--161, doi: 10.1002/jgt.3190200205.
[3]	C. Berge, Graphs (North-Holland, Amsterdam New York, 1985).
[4]	F. Boesch and R. Tindell, Robbins Theorem for mixed multigraphs, Amer. Math. Monthly 87 (1980) 716--719, doi: 10.2307/2321858.
[5]	R.A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory (Encyclopedia of Mathematics and its Applications) (Cambridge University Press, 1991).
[6]	R. Diestel, Graph Theory 3rd Edition (Springer-Verlag, Berlin Heidelberg New York, 2005).
[7]	H. Galeana-Sánchez, I.A. Goldfeder and I. Urrutia, On the structure of 3-quasi-transitive digraphs, Discrete Math. 310 (2010) 2495--2498, doi: 10.1016/j.disc.2010.06.008.
[8]	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.
[9]	C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205--219, doi: 10.7151/dmgt.1613.
[10]	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.

Received 25 May 2011
Revised 22 February 2012
Accepted 23 February 2012