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