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

César Hernández-Cruz

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 247-260
  • 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 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.

How to cite

top

Cé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. [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[Crossref] Zbl0832.05048
  3. [3] C. Berge, Graphs (North-Holland, Amsterdam New York, 1985). 
  4. [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. [5] R.A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory (Encyclopedia of Mathematics and its Applications) (Cambridge University Press, 1991). 
  6. [6] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag, Berlin Heidelberg New York, 2005). 
  7. [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. [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. [9] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613[Crossref] 
  10. [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] 

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.