# Some Remarks On The Structure Of Strong K-Transitive Digraphs

César Hernández-Cruz; Juan José Montellano-Ballesteros

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 4, page 651-671
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topCésar Hernández-Cruz, and Juan José Montellano-Ballesteros. "Some Remarks On The Structure Of Strong K-Transitive Digraphs." Discussiones Mathematicae Graph Theory 34.4 (2014): 651-671. <http://eudml.org/doc/269824>.

@article{CésarHernández2014,

abstract = {A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.},

author = {César Hernández-Cruz, Juan José Montellano-Ballesteros},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraph; transitive digraph; k-transitive digraph; quasi-transitive digraph; k-quasi-transitive digraph; Laborde-Payan-Xuong Conjecture.; -transitive digraph; -quasi-transitive digraph; Laborde-Payan-Xuong conjecture},

language = {eng},

number = {4},

pages = {651-671},

title = {Some Remarks On The Structure Of Strong K-Transitive Digraphs},

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

volume = {34},

year = {2014},

}

TY - JOUR

AU - César Hernández-Cruz

AU - Juan José Montellano-Ballesteros

TI - Some Remarks On The Structure Of Strong K-Transitive Digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 4

SP - 651

EP - 671

AB - A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.

LA - eng

KW - digraph; transitive digraph; k-transitive digraph; quasi-transitive digraph; k-quasi-transitive digraph; Laborde-Payan-Xuong Conjecture.; -transitive digraph; -quasi-transitive digraph; Laborde-Payan-Xuong conjecture

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

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] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag Berlin, Heidelberg New York, 2005).
- [3] 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
- [4] A. Ghouila-Houri, Caract´erisation des graphes non orient´es dont on peut orienterles arrˆetes de mani`ere `a obtenir le graphe d’une relation d’ordre, C. R. Acad. Sci. Paris 254 (1962) 1370-1371.
- [5] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613
- [6] C. Hernández-Cruz, 4-transitive digraphs I: The structure of strong 4-transitive di- graphs, Discuss. Math. Graph Theory 33 (2013) 247-260. doi:10.7151/dmgt.1645 Zbl1293.05136
- [7] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other Combinatorial Topics, Prague, M. Fiedler (Ed(s)), (Teubner, Leipzig, 1983) 173-177. Zbl0528.05034
- [8] R. Wang, A conjecture on k-transitive digraphs, Discrete Math. 312 (2012) 1458-1460. doi:0.1016/j.disc.2012.01.011 Zbl1237.05092
- [9] R. Wang and S. Wang, Underlying graphs of 3-quasi-transitive digraphs and 3- transitive digraphs, Discuss. Math. Graph Theory 33 (2013) 429-436. doi:10.7151/dmgt.1680 Zbl1293.05141

## Citations in EuDML Documents

top## NotesEmbed ?

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