Some Remarks On The Structure Of Strong K-Transitive Digraphs

Cé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 -