Let D = (V (D),A(D)) be a digraph and k ≥ 2 be an integer. A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v) ≥ k; it is l-absorbent if for every u ∈ V (D) − N, there exists v ∈ N such that d(u, v) ≤ l. A (k, l)-kernel of D is a k-independent and l-absorbent subset of V (D). A k-kernel is a (k, k − 1)-kernel. A digraph D is k-transitive if for any path x0x1 ・ ・ ・ xk of length k, x0 dominates xk. Hernández-Cruz [3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219] proved that a 3-transitive digraph has a 2-kernel if and only if it has no terminal strong component isomorphic to a 3-cycle. In this paper, we generalize the result to strong k-transitive digraphs and prove that a strong k-transitive digraph with k ≥ 4 has a (k − 1)-kernel if and only if it is not isomorphic to a k-cycle.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v,w ∈ V (D), (u, v), (v,w) ∈ A(D) implies that (u,w) ∈ A(D). This concept can be generalized as follows: A digraph is k-transitive if for every u, v ∈ V (D), the existence of a uv-directed path of length k in D implies that (u, v) ∈ A(D). A very useful structural characterization of transitive digraphs has been known for a long time, and recently, 3-transitive digraphs have been characterized. In this work, some general structural results are proved for k-transitive digraphs with arbitrary k ≥ 2. Some of this results are used to characterize the family of 4-transitive digraphs. Also some of the general results remain valid for k-quasi-transitive digraphs considering an additional hypothesis. A conjecture on a structural property of k-transitive digraphs is proposed.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.