Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Laborde-Payan-Xuong Conjecture

Sortuj według:

Ogranicz wyniki do:

Some Results on 4-Transitive Digraphs

100%

García-Vázquez P. R., Hernández-Cruz C.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 1

117-129

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 García-Vázquez P. R.

1 Hernández-Cruz C.

1 2017

Wyniki wyszukiwania

Some Results on 4-Transitive Digraphs