SOME RESULTS ON 4-TRANSITIVE DIGRAPHS

作者：Ricardo Garcia Vazquez Patricio; Hernandez Cruz Cesar

来源：Discussiones Mathematicae - Graph Theory, 2017, 37(1): 117-129.

DOI：10.7151/dmgt.1922

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

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 is an element of V, the existence of a uv-path of length k in D implies that (u, v) E 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 is an element of N, we have d(u, v), d(v, u) >= k; it is l-absorbent if for every u is an element of V \ N there exists v is an element of N such that d(u, v) <= 1. 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.

• 出版日期2017-2