TITLE

# 3-TRANSITIVE DIGRAPHS

AUTHOR(S)
HERNÁANDEZ-CRUZ, CÉESAR
PUB. DATE
May 2012
SOURCE
Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 2, p205
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
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 3-transitive if the existence of the directed path (u; v;w; x) of length 3 in D implies the existence of the arc (u; x) Îµ A(D). In this article strong 3-transitive digraphs are characterized and the structure of non-strong 3-transitive digraphs is described. The results are used, e.g., to characterize 3-transitive digraphs that are transitive and to characterize 3-transitive digraphs with a kernel.
ACCESSION #
86440287

## Related Articles

• ON THE EXISTENCE OF (k,l)-KERNELS IN INFINITE DIGRAPHS: A SURVEY. GALEANA-SÁNCHEZ, H.; HERNÁNDEZ-CRUZ, C. // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 3, p431

Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k, l)-kernel N of D is a k-independent (if u, v âˆˆ N, u â‰  v, then d(u, v), d(v, u) â‰¥ k) and l-absorbent (if u âˆˆ V (D) - N then there exists v âˆˆ N such that d(u, v)...

• 3-TRANSITIVE DIGRAPHS. Hernández-Cruz, César // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 3, p205

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 3-transitive if the existence of the directed path (u; v;w; x) of length 3 in D implies the existence of the arc (u, x) âˆˆ A(D). In this article strong 3-transitive digraphs are...

• ON (k; l)-KERNELS IN D-JOIN OF DIGRAPHS. Szumny, Waldemar; Wloch, Andrzej; Wloch, Iwona // Discussiones Mathematicae: Graph Theory;2007, Vol. 27 Issue 3, p457

In [5] the necessary and sufficient conditions for the existence of (k; l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k;...

• An Algorithm to Detect Cycle in an Undirected Graph. Kumar, Anand; Jani, N. N. // International Journal of Computational Intelligence Research;2010, Vol. 6 Issue 2, p305

This paper presents a novel algorithm to detect cycles in a graph. The graph may be of any type. Cycles are available in a graph and in much real life application; it is required to know the existence of cycles in a graph. This algorithm is developed in the context of network design problem but...

• SOME REMARKS ON THE STRUCTURE OF STRONG k-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR; MONTELLANO-BALLESTEROS, JUAN JOSÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p651

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...

• k-KERNELS IN GENERALIZATIONS OF TRANSITIVE DIGRAPHS. GALEANA-SÁNCHEZ, HORTENSIA; HERNÁNDEZ-CRUZ, CÉSAR // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p293

No abstract available.

• KERNELS BY MONOCHROMATIC PATHS AND THE COLOR-CLASS DIGRAPH. GALEANA-SÁNCHEZ, HORTENSIA // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p273

No abstract available.

• THE i-CHORDS OF CYCLES AND PATHS. MCKEE, TERRY A. // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 4, p607

An i-chord of a cycle or path is an edge whose endpoints are a distance i â‰¥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results...

• Countable Markov shifts with transient potentials. Cyr, Van // Proceedings of the London Mathematical Society;Dec2011, Vol. 103 Issue 6, p923

We define a simple property on an infinite directed graph î”¦ and show that it is necessary and sufficient for the existence of a transient potential on the associated countable Markov shift.

Share