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
Academic Journal
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

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics