Some Results on 4-Transitive Digraphs

• Autorzy: Patricio Ricardo García-Vázquez , César Hernández-Cruz
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

4-transitive digraph; k-transitive digraph; 3-kernel; k-kernel; Laborde-Payan-Xuong Conjecture

Kategorie tematyczne

• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 117-129

Daty

wydano

2017-02-01

otrzymano

2015-02-14

poprawiono

2016-02-25

zaakceptowano

2016-02-25

online

2017-01-13

Twórcy

autor

Patricio Ricardo García-Vázquez

• Facultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad Universitaria, , D.F.

autor

César Hernández-Cruz

• Facultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad Universitaria, , D.F.

Identyfikatory

DOI

10.7151/dmgt.1922