Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

(K − 1)-Kernels In Strong K-Transitive Digraphs

100%

Wang R.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 2

229-235

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.

Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs

63%

Wang R., Wang S.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 2

429-435

A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). C´esar Hern´andez-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation. In this paper, we shall prove that the conjecture is true.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Wang R.

1 Wang S.

1 2015

1 2013

Wyniki wyszukiwania

(K − 1)-Kernels In Strong K-Transitive Digraphs

Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs