A note on kernels and solutions in digraphs

Matúš Harminc; Roman Soták

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

Displaying similar documents to “A note on kernels and solutions in digraphs”

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

Which directed graphs have a solution?

Mehdi Behzad, Frank Harary (1977)

Mathematica Slovaca

Similarity:

On (k,l)-kernels in D-join of digraphs

Waldemar Szumny, Andrzej Włoch, Iwona Włoch (2007)

Discussiones Mathematicae Graph Theory

Similarity:

In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.

On Hallian digraphs and their binding number

Mieczysław Borowiecki, Danuta Michalak (1989)

Banach Center Publications

Similarity:

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

On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey

H. Galeana-Sánchez, C. Hernández-Cruz (2014)

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 (if u, v ∈ N, u 6= v, then d(u, v), d(v, u) ≥ k) and l-absorbent (if u ∈ V (D) − N then there exists v ∈ N such that d(u, v) ≤ l) set of vertices. A k-kernel is a (k, k −1)-kernel. This work is a survey of results proving sufficient conditions for the existence of (k, l)-kernels in infinite digraphs. Despite all the previous work in this direction...

k-kernels in generalizations of transitive digraphs

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, u ≠ v, then d(u,v), d(v,u) ≥ 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. Quasi-transitive, right-pretransitive and left-pretransitive digraphs are generalizations of transitive digraphs. In this paper the following results are proved:...

Comparing a Cayley digraph with its reverse.

Abas, M. (2000)

Acta Mathematica Universitatis Comenianae. New Series

Similarity:

A note on removing a point of a strong digraph

Peter Horák (1983)

Mathematica Slovaca

Similarity:

Sharp Upper Bounds on the Signless Laplacian Spectral Radius of Strongly Connected Digraphs

Weige Xi, Ligong Wang (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V (G),E(G)) be a simple strongly connected digraph and q(G) be the signless Laplacian spectral radius of G. For any vertex vi ∈ V (G), let d+i denote the outdegree of vi, m+i denote the average 2-outdegree of vi, and N+i denote the set of out-neighbors of vi. In this paper, we prove that: (1) (1) q(G) = d+1 +d+2 , (d+1 ≠ d+2) if and only if G is a star digraph [...] ,where d+1, d+2 are the maximum and the second maximum outdegree, respectively [...] is the digraph on n vertices...

On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect

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

Discussiones Mathematicae Graph Theory

Similarity:

A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel. We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows: V( ζ(D)) = V(D), and A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic...