# 4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 2, page 247-260
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topCésar Hernández-Cruz. "4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs." Discussiones Mathematicae Graph Theory 33.2 (2013): 247-260. <http://eudml.org/doc/267746>.

@article{CésarHernández2013,

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.},

author = {César Hernández-Cruz},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraph; transitive digraph; quasi-transitive digraph; 4-transitive digraph; k-transitive digraph; k-quasi-transitive digraph; -transitive digraph; -quasi-transitive graph},

language = {eng},

number = {2},

pages = {247-260},

title = {4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs},

url = {http://eudml.org/doc/267746},

volume = {33},

year = {2013},

}

TY - JOUR

AU - César Hernández-Cruz

TI - 4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 2

SP - 247

EP - 260

AB - 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.

LA - eng

KW - digraph; transitive digraph; quasi-transitive digraph; 4-transitive digraph; k-transitive digraph; k-quasi-transitive digraph; -transitive digraph; -quasi-transitive graph

UR - http://eudml.org/doc/267746

ER -

## References

top- [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag, Berlin Heidelberg New York, 2002). Zbl1001.05002
- [2] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161. doi:10.1002/jgt.3190200205[Crossref] Zbl0832.05048
- [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[Crossref] Zbl0453.05026
- [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-quasitransitive digraphs, Discrete Math. 310 (2010) 2495-2498. doi:10.1016/j.disc.2010.06.008[Crossref]
- [8] H. Galeana-Sánchez and C. Hern´andez-Cruz, k-kernels in k-transitive and k-quasitransitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005[WoS][Crossref]
- [9] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613[Crossref]
- [10] S.Wang and R.Wang, Independent sets and non-augmentable paths in arc-locally insemicomplete digraphs and quasi-arc-transitive digraphs, Discrete Math. 311 (2010) 282-288. doi:10.1016/j.disc.2010.11.009[WoS][Crossref]