- Tytuł:
- Some Results on 4-Transitive Digraphs
- Autorzy:
-
García-Vázquez, Patricio Ricardo
Hernández-Cruz, César - Powiązania:
- https://bibliotekanauki.pl/articles/31342166.pdf
- Data publikacji:
- 2017-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
4-transitive digraph
k -transitive digraph
3-kernel
k -kernel
Laborde-Payan-Xuong Conjecture - Opis:
- 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 NP-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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 117-129
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł