# 3-transitive digraphs

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 2, page 205-219
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topCésar Hernández-Cruz. "3-transitive digraphs." Discussiones Mathematicae Graph Theory 32.2 (2012): 205-219. <http://eudml.org/doc/270928>.

@article{CésarHernández2012,

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 3-transitive if the existence of the directed path (u,v,w,x) of length 3 in D implies the existence of the arc (u,x) ∈ A(D). In this article strong 3-transitive digraphs are characterized and the structure of non-strong 3-transitive digraphs is described. The results are used, e.g., to characterize 3-transitive digraphs that are transitive and to characterize 3-transitive digraphs with a kernel.},

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

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraph; kernel; transitive digraph; quasi-transitive digraph; 3-transitive digraph; 3-quasi-transitive digraph},

language = {eng},

number = {2},

pages = {205-219},

title = {3-transitive digraphs},

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

volume = {32},

year = {2012},

}

TY - JOUR

AU - César Hernández-Cruz

TI - 3-transitive digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 2

SP - 205

EP - 219

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 3-transitive if the existence of the directed path (u,v,w,x) of length 3 in D implies the existence of the arc (u,x) ∈ A(D). In this article strong 3-transitive digraphs are characterized and the structure of non-strong 3-transitive digraphs is described. The results are used, e.g., to characterize 3-transitive digraphs that are transitive and to characterize 3-transitive digraphs with a kernel.

LA - eng

KW - digraph; kernel; transitive digraph; quasi-transitive digraph; 3-transitive digraph; 3-quasi-transitive digraph

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

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. Zbl0832.05048
- [3] J. Bang-Jensen, J. Huang and E. Prisner, In-tournament digraphs, J. Combin. Theory (B) 59 (1993) 267-287, doi: 10.1006/jctb.1993.1069. Zbl0794.05033
- [4] C. Berge, Graphs (North-Holland, Amsterdam New York, 1985).
- [5] E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, Discrete Math. 306 (2006) 2336-2354, doi: 10.1016/j.disc.2005.12.031. Zbl1103.05034
- [6] V. Chvátal, On the computational complexity of finding a kernel, Report No. CRM-300, 1973, Centre de recherches mathématiques, Université de Montréal.
- [7] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag Berlin Heidelberg New York, 2005).
- [8] H. Galeana-Sánchez and I.A. Goldfeder, A classification of arc-locally semicomplete digraphs, Publicaciones Preliminares del Instituto de Matemáticas, UNAM 859 (2010). Zbl1272.05063
- [9] 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. Zbl1213.05112
- [10] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in k-transitive and k-quasi-transitive digraphs, Submitted (2010).
- [11] A. Ghouila-Houri, Caractérization des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'rdre, Comptes Rendus de l'Académie des Sciences Paris 254 (1962) 1370-1371. Zbl0105.35503
- [12] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1953). Zbl0053.09303
- [13] S. Wang and R. Wang, The structure of arc-locally in-semicomplete digraphs, Discrete Math. 309 (2009) 6555-6562, doi: 10.1016/j.disc.2009.06.033. Zbl1183.05032
- [14] 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. Zbl1222.05090

## Citations in EuDML Documents

top- Ruixia Wang, Shiying Wang, Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs
- César Hernández-Cruz, 4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs
- Ruixia Wang, (K − 1)-Kernels In Strong K-Transitive Digraphs
- César Hernández-Cruz, Juan José Montellano-Ballesteros, Some Remarks On The Structure Of Strong K-Transitive Digraphs

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.