Displaying similar documents to “Strong asymmetric digraphs with prescribed interior and annulus”

On a problem of walks

Charles Delorme, Marie-Claude Heydemann (1999)

Annales de l'institut Fourier

Similarity:

In 1995, F. Jaeger and M.-C. Heydemann began to work on a conjecture on binary operations which are related to homomorphisms of De Bruijn digraphs. For this, they have considered the class of digraphs G such that for any integer k , G has exactly n walks of length k , where n is the order of G . Recently, C. Delorme has obtained some results on the original conjecture. The aim of this paper is to recall the conjecture and to report where all the authors arrived.

Cyclically k-partite digraphs and k-kernels

Hortensia Galeana-Sánchez, César Hernández-Cruz (2011)

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 (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N then d(u,v) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. A digraph D is cyclically k-partite if there exists a partition V i i = 0 k - 1 of V(D) such that every arc in D is a V i V i + 1 - a r c (mod k). We give a characterization for an unilateral digraph to be cyclically k-partite through...

k-Kernels and some operations in digraphs

Hortensia Galeana-Sanchez, Laura Pastrana (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph. V(D) denotes the set of vertices of D; a set N ⊆ V(D) is said to be a k-kernel of D if it satisfies the following two conditions: for every pair of different vertices u,v ∈ N it holds that every directed path between them has length at least k and for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an xy-directed path of length at most k-1. In this paper, we consider some operations on digraphs and prove the existence of k-kernels in digraphs formed...

Kernels in the closure of coloured digraphs

Hortensia Galeana-Sánchez, José de Jesús García-Ruvalcaba (2000)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph with V(D) and A(D) the sets of vertices and arcs of D, respectively. A kernel of D is a set I ⊂ V(D) such that no arc of D joins two vertices of I and for each x ∈ V(D)∖I there is a vertex y ∈ I such that (x,y) ∈ A(D). A digraph is kernel-perfect if every non-empty induced subdigraph of D has a kernel. If D is edge coloured, we define the closure ξ(D) of D the multidigraph with V(ξ(D)) = V(D) and A ( ξ ( D ) ) = ⋃ i ( u , v ) w i t h c o l o u r i t h e r e e x i s t s a m o n o c h r o m a t i c p a t h o f c o l o u r i f r o m t h e v e r t e x u t o t h e v e r t e x v c o n t a i n e d i n D . Let T₃ and C₃ denote the transitive tournament of order 3 and the 3-cycle,...