The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Counting unlabelled topologies and transitive relations.”

4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs

César Hernández-Cruz (2013)

Discussiones Mathematicae Graph Theory

Similarity:

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

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

Ruixia Wang, Shiying Wang (2013)

Discussiones Mathematicae Graph Theory

Similarity:

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.

Frucht’s Theorem for the Digraph Factorial

Richard H. Hammack (2013)

Discussiones Mathematicae Graph Theory

Similarity:

To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. A new operation on digraphs was introduced recently as an aid in solving certain questions regarding cancellation over the direct product of digraphs. Given a digraph A, its factorial A! is certain digraph whose vertex set is the permutations of V (A). The arc set E(A!) forms...

3-transitive digraphs

César Hernández-Cruz (2012)

Discussiones Mathematicae Graph Theory

Similarity:

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

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

Ruixia Wang (2015)

Discussiones Mathematicae Graph Theory

Similarity:

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

Some Remarks On The Structure Of Strong K-Transitive Digraphs

César Hernández-Cruz, Juan José Montellano-Ballesteros (2014)

Discussiones Mathematicae Graph Theory

Similarity:

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 acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least...