Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: 3-kernel

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.

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs

86%

Hell P., Hernández-Cruz C.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 1

167-185

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) 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 (D) − 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 (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Hernández-Cruz C.

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

1 Hell P.

1 2017

1 2014

Wyniki wyszukiwania

Some Results on 4-Transitive Digraphs

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs