Some Results on 4-Transitive Digraphs

Patricio Ricardo García-Vázquez, and César Hernández-Cruz. "Some Results on 4-Transitive Digraphs." Discussiones Mathematicae Graph Theory 37.1 (2017): 117-129. <http://eudml.org/doc/288000>.

@article{PatricioRicardoGarcía2017,
abstract = {Let D be a digraph with set of vertices V and set of arcs A. We say that D is k-transitive if for every pair of vertices u, v ∈ V, the existence of a uv-path of length k in D implies that (u, v) ∈ A. A 2-transitive digraph is a transitive digraph in the usual sense. A subset N of V is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V. The problem of determining whether a digraph has a k-kernel is known to be -complete for every k ≥ 2. In this work, we characterize 4-transitive digraphs having a 3-kernel and also 4-transitive digraphs having a 2-kernel. Using the latter result, a proof of the Laborde-Payan-Xuong conjecture for 4-transitive digraphs is given. This conjecture establishes that for every digraph D, an independent set can be found such that it intersects every longest path in D. Also, Seymour’s Second Neighborhood Conjecture is verified for 4-transitive digraphs and further problems are proposed.},
author = {Patricio Ricardo García-Vázquez, César Hernández-Cruz},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {4-transitive digraph; k-transitive digraph; 3-kernel; k-kernel; Laborde-Payan-Xuong Conjecture; -transitive digraph; -kernel; Laborde-Payan-Xuong conjecture},
language = {eng},
number = {1},
pages = {117-129},
title = {Some Results on 4-Transitive Digraphs},
url = {http://eudml.org/doc/288000},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Patricio Ricardo García-Vázquez
AU - César Hernández-Cruz
TI - Some Results on 4-Transitive Digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 117
EP - 129
AB - Let D be a digraph with set of vertices V and set of arcs A. We say that D is k-transitive if for every pair of vertices u, v ∈ V, the existence of a uv-path of length k in D implies that (u, v) ∈ A. A 2-transitive digraph is a transitive digraph in the usual sense. A subset N of V is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V. The problem of determining whether a digraph has a k-kernel is known to be -complete for every k ≥ 2. In this work, we characterize 4-transitive digraphs having a 3-kernel and also 4-transitive digraphs having a 2-kernel. Using the latter result, a proof of the Laborde-Payan-Xuong conjecture for 4-transitive digraphs is given. This conjecture establishes that for every digraph D, an independent set can be found such that it intersects every longest path in D. Also, Seymour’s Second Neighborhood Conjecture is verified for 4-transitive digraphs and further problems are proposed.
LA - eng
KW - 4-transitive digraph; k-transitive digraph; 3-kernel; k-kernel; Laborde-Payan-Xuong Conjecture; -transitive digraph; -kernel; Laborde-Payan-Xuong conjecture
UR - http://eudml.org/doc/288000
ER -