TITLE

4-TRANSITIVE DIGRAPHS I: THE STRUCTURE OF STRONG 4-TRANSITIVE DIGRAPHS

AUTHOR(S)
HERNÁNDEZ-CRUZ, CÉSAR
PUB. DATE
July 2013
SOURCE
Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p247
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 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.
ACCESSION #
86720980

 

Related Articles

  • On Sullivan's conjecture on cycles in 4-free and 5-free digraphs. Liang, Hao; Xu, Jun // Acta Mathematica Sinica;Jan2013, Vol. 29 Issue 1, p53 

    For a simple digraph G, let β( G) be the size of the smallest subset X ⊆ E( G) such that G−X has no directed cycles, and let γ( G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This...

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

  • A Characterization of Directed Paths. S., Ramya.; M., Nagesh. H. // International Journal of Mathematical Combinatorics;Jun2015, Vol. 2, p144 

    In this note, the non-trivial connected digraphs D with vertex set V (D) = {v1, v2, ..., vn} satisfying ... are characterized, where d- (vi) and d+ (vi) be the in-degree and out-degree of vertices of D, respectively.

  • $$\varPi $$ -Kernels in Digraphs. Galeana-Sánchez, Hortensia; Montellano-Ballesteros, Juan // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2207 

    Let $$D=(V(D), A(D))$$ be a digraph, $$DP(D)$$ be the set of directed paths of $$D$$ and let $$\varPi $$ be a subset of $$DP(D)$$ . A subset $$S\subseteq V(D)$$ will be called $$\varPi $$ -independent if for any pair $$\{x, y\} \subseteq S$$ , there is no $$xy$$ -path nor $$yx$$ -path in...

  • The Spectrum of Tetrahedral Quadruple Systems. Wang, Jian; Liang, Miao; Du, Beiliang // Graphs & Combinatorics;Jul2011, Vol. 27 Issue 4, p593 

    n ordered analogue of quadruple systems is tetrahedral quadruple systems. A tetrahedral quadruple system of order v and index λ, TQS( v, λ), is a pair $${(S, \mathcal{T})}$$ where S is a finite set of v elements and $${\mathcal{T}}$$ is a family of oriented tetrahedrons of elements of S...

  • SOME RESULTS ON SEMI-TOTAL SIGNED GRAPHS. SINHA, DEEPA; GARG, PRAVIN // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 4, p625 

    A signed graph (or sigraph in short) is an ordered pair S = (Suδ), where Su is a graph G = (V,E), called the underlying graph of S and δ : E → {+,-} is a function from the edge set E of Suinto the set {+,-}, called the signature of S. The x-line sigraph of S denoted by L x (S) is a...

  • Structural Learning about Directed Acyclic Graphs from Multiple Databases. Qiang Zhao // Abstract & Applied Analysis;2012, p1 

    We propose an approach for structural learning of directed acyclic graphs from multiple databases. We first learn a local structure from each database separately, and then we combine these local structures together to construct a global graph over all variables. In our approach, we do not...

  • UNDERLYING GRAPHS OF 3-QUASI-TRANSITIVE DIGRAPHS AND 3-TRANSITIVE DIGRAPHS RUIXIA WANG, SHIYING WANG. RUIXIA WANG; SHIYING WANG // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p429 

    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ésar Hernández-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation....

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

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

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

Try another library?
Sign out of this library

Other Topics