TITLE

$$\varPi$$ -Kernels in Digraphs

AUTHOR(S)
Galeana-Sánchez, Hortensia; Montellano-Ballesteros, Juan
PUB. DATE
November 2015
SOURCE
Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2207
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
Let $$D=(V(D), A(D))$$ be a digraph, $$DP(D)$$ be the set of directed paths of $$D$$ and let $$\varPi$$ be a subset of $$DP(D)$$ . A subset $$S\subseteq V(D)$$ will be called $$\varPi$$ -independent if for any pair $$\{x, y\} \subseteq S$$ , there is no $$xy$$ -path nor $$yx$$ -path in $$\varPi$$ ; and will be called $$\varPi$$ -absorbing if for every $$x\in V(D)\setminus S$$ there is $$y\in S$$ such that there is an $$xy$$ -path in $$\varPi$$ . A set $$S\subseteq V(D)$$ will be called a $$\varPi$$ -kernel if $$S$$ is $$\varPi$$ -independent and $$\varPi$$ -absorbing. This concept generalize several 'kernel notions' like kernel or kernel by monochromatic paths, among others. In this paper we present some sufficient conditions for the existence of $$\varPi$$ -kernels.
ACCESSION #
110606512

Related Articles

• 4-TRANSITIVE DIGRAPHS I: THE STRUCTURE OF STRONG 4-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p247

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

• 3-TRANSITIVE DIGRAPHS. Hernández-Cruz, César // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 3, p205

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

• On Sullivan's conjecture on cycles in 4-free and 5-free digraphs. Liang, Hao; Xu, Jun // Acta Mathematica Sinica;Jan2013, Vol. 29 Issue 1, p53

For a simple digraph G, let Î²( G) be the size of the smallest subset X âŠ† E( G) such that Gâˆ’X has no directed cycles, and let Î³( G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This...

• A Characterization of Directed Paths. S., Ramya.; M., Nagesh. H. // International Journal of Mathematical Combinatorics;Jun2015, Vol. 2, p144

In this note, the non-trivial connected digraphs D with vertex set V (D) = {v1, v2, ..., vn} satisfying ... are characterized, where d- (vi) and d+ (vi) be the in-degree and out-degree of vertices of D, respectively.

• KERNELS BY MONOCHROMATIC PATHS AND THE COLOR-CLASS DIGRAPH. GALEANA-SÁNCHEZ, HORTENSIA // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p273

No abstract available.

• k-KERNELS IN GENERALIZATIONS OF TRANSITIVE DIGRAPHS. GALEANA-SÁNCHEZ, HORTENSIA; HERNÁNDEZ-CRUZ, CÉSAR // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p293

No abstract available.

• Î³-CYCLES AND TRANSITIVITY BY MONOCHROMATIC PATHS IN ARC-COLOURED DIGRAPHS. CASAS-BAUTISTA, ENRIQUE; GALEANA-SÁNCHEZ, HORTENSIA; ROJAS-MONROY, ROCÍO // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 3, p493

We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. If D is an m-coloured digraph and a âˆˆ A(D), colour(a) will denote the colour has been used on a. A path (or a cycle) is called monochromatic if all of its arcs are coloured alike. A Î³-cycle in D is a...

• A Contribution to the Second Neighborhood Problem. Ghazal, Salman // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1365

Seymour's Second Neighborhood Conjecture asserts that every oriented graph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. It is proved for tournaments, tournaments missing a matching and tournaments missing a generalized star. We...

• SOME RESULTS ON SEMI-TOTAL SIGNED GRAPHS. SINHA, DEEPA; GARG, PRAVIN // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 4, p625

A signed graph (or sigraph in short) is an ordered pair S = (SuÎ´), where Su is a graph G = (V,E), called the underlying graph of S and Î´ : E â†’ {+,-} is a function from the edge set E of Suinto the set {+,-}, called the signature of S. The x-line sigraph of S denoted by L x (S) is a...

Share