Page 1 Next

Displaying 1 – 20 of 500

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 bound for the rank-one transient of inhomogeneous matrix products in special case

Arthur Kennedy-Cochran-Patrick, Sergeĭ Sergeev, Štefan Berežný (2019)

Kybernetika

We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.

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 500

Page 1 Next