Cyclically k-partite digraphs and k-kernels

Hortensia Galeana-Sánchez; César Hernández-Cruz

Displaying similar documents to “Cyclically k-partite digraphs and k-kernels”

Strong asymmetric digraphs with prescribed interior and annulus

Steven J. Winters (2001)

Czechoslovak Mathematical Journal

Similarity:

The directed distance $d (u, v)$ from $u$ to $v$ in a strong digraph $D$ is the length of a shortest $u - v$ path in $D$ . The eccentricity $e (v)$ of a vertex $v$ in $D$ is the directed distance from $v$ to a vertex furthest from $v$ in $D$ . The center and periphery of a strong digraph are two well known subdigraphs induced by those vertices of minimum and maximum eccentricities, respectively. We introduce the interior and annulus of a digraph which are two induced subdigraphs involving the remaining vertices. Several results...

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

Monochromatic cycles and monochromatic paths in arc-colored digraphs

Hortensia Galeana-Sánchez, Guadalupe Gaytán-Gómez, Rocío Rojas-Monroy (2011)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-colored digraph if the arcs of D are colored with m colors. A path (or a cycle) is called monochromatic if all of its arcs are colored alike. A cycle is called a quasi-monochromatic cycle if with at most one exception all of its arcs are colored alike. A subdigraph H in D is called rainbow if all its arcs have different colors. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different...

A sufficient condition for the existence of k-kernels in digraphs

H. Galeana-Sánchez, H.A. Rincón-Mejía (1998)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel. This result generalizes some previous...

Which directed graphs have a solution?

Mehdi Behzad, Frank Harary (1977)

Mathematica Slovaca

Similarity:

Monochromatic kernel-perfectness of special classes of digraphs

Hortensia Galeana-Sánchez, Luis Alberto Jiménez Ramírez (2007)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we introduce the concept of monochromatic kernel-perfect digraph, and we prove the following two results: (1) If D is a digraph without monochromatic directed cycles, then D and each $α_{v}, v \in V (D)$ are monochromatic kernel-perfect digraphs if and only if the composition over D of ${(α_{v})}_{v \in V (D)}$ is a monochromatic kernel-perfect digraph. (2) D is a monochromatic kernel-perfect digraph if and only if for any B ⊆ V(D), the duplication of D over B, $D^{B}$ , is a monochromatic kernel-perfect digraph. ...

Competition hypergraphs of digraphs with certain properties II. Hamiltonicity

Martin Sonntag, Hanns-Martin Teichert (2008)

Discussiones Mathematicae Graph Theory

Similarity:

If D = (V,A) is a digraph, its competition hypergraph (D) has vertex set V and e ⊆ V is an edge of (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that $e = N_{D} ⁻ (v) = w \in V | (w, v) \in A$ . We give characterizations of (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].

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.

Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V(D)-N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel-perfect digraph. In this paper I investigate some sufficient conditions for a digraph to have a kernel by asking for the existence of certain diagonals or symmetrical arcs in each odd directed cycle whose length is at most 2α(D)+1, where α(D) is the maximum cardinality of an independent...

Characterization of power digraphs modulo $n$

Uzma Ahmad, Syed Husnine (2011)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

A power digraph modulo $n$ , denoted by $G (n, k)$ , is a directed graph with $Z_{n} = {0, 1, \dots, n - 1}$ as the set of vertices and $E = {(a, b) : a^{k} \equiv b (mod n)}$ as the edge set, where $n$ and $k$ are any positive integers. In this paper we find necessary and sufficient conditions on $n$ and $k$ such that the digraph $G (n, k)$ has at least one isolated fixed point. We also establish necessary and sufficient conditions on $n$ and $k$ such that the digraph $G (n, k)$ contains exactly two components. The primality of Fermat number is also discussed.

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

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs

Pavol Hell, César Hernández-Cruz (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in...