Page 1 Next

Displaying 1 – 20 of 496

Showing per page

3-transitive digraphs

César Hernández-Cruz (2012)

Discussiones Mathematicae Graph Theory

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

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

César Hernández-Cruz (2013)

Discussiones Mathematicae Graph Theory

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

A class of tight circulant tournaments

Hortensia Galeana-Sánchez, Víctor Neumann-Lara (2000)

Discussiones Mathematicae Graph Theory

A tournament is said to be tight whenever every 3-colouring of its vertices using the 3 colours, leaves at least one cyclic triangle all whose vertices have different colours. In this paper, we extend the class of known tight circulant tournaments.

A conjecture on cycle-pancyclism in tournaments

Hortensia Galeana-Sánchez, Sergio Rajsbaum (1998)

Discussiones Mathematicae Graph Theory

Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote I γ ( C ) = | A ( γ ) A ( C ) | , the number of arcs that γ and Cₖ have in common. Let f ( k , T , γ ) = m a x I γ ( C ) | C T and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave...

A deceptive fact about functions

Wiesław Dziobiak, Andrzej Ehrenfeucht, Jacqueline Grace, Donald Silberger (2000)

Fundamenta Mathematicae

The paper provides a proof of a combinatorial result which pertains to the characterization of the set of equations which are solvable in the composition monoid of all partial functions on an infinite set.

A note on arc-disjoint cycles in tournaments

Jan Florek (2014)

Colloquium Mathematicae

We prove that every vertex v of a tournament T belongs to at least m a x m i n δ ( T ) , 2 δ ( T ) - d T ( v ) + 1 , m i n δ ¯ ( T ) , 2 δ ¯ ( T ) - d ¯ T ( v ) + 1 arc-disjoint cycles, where δ⁺(T) (or δ¯(T)) is the minimum out-degree (resp. minimum in-degree) of T, and d T ( v ) (or d ¯ T ( v ) ) is the out-degree (resp. in-degree) of v.

A note on kernels and solutions in digraphs

Matúš Harminc, Roman Soták (1999)

Discussiones Mathematicae Graph Theory

For given nonnegative integers k,s an upper bound on the minimum number of vertices of a strongly connected digraph with exactly k kernels and s solutions is presented.

Currently displaying 1 – 20 of 496

Page 1 Next