3-transitive digraphs

César Hernández-Cruz

Discussiones Mathematicae Graph Theory (2012)

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

Abstract

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

How to cite

top

Cé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. [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag Berlin Heidelberg New York, 2002). Zbl1001.05002
  2. [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. [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. [4] C. Berge, Graphs (North-Holland, Amsterdam New York, 1985). 
  5. [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. [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. [7] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag Berlin Heidelberg New York, 2005). 
  8. [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. [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. [10] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in k-transitive and k-quasi-transitive digraphs, Submitted (2010). 
  11. [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. [12] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1953). Zbl0053.09303
  13. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.