𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Disjoint quasi-kernels in digraphs

✍ Scribed by Scott Heard; Jing Huang

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
126 KB
Volume
58
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A quasi‐kernel in a digraph is an independent set of vertices such that any vertex in the digraph can reach some vertex in the set via a directed path of length at most two. Chvátal and Lovász proved that every digraph has a quasi‐kernel. Recently, Gutin et al. raised the question of which digraphs have a pair of disjoint quasi‐kernels. Clearly, a digraph has a pair of disjoint quasi‐kernels cannot contain sinks, that is, vertices of outdegree zero, as each such vertex is necessarily included in a quasi‐kernel. However, there exist digraphs which contain neither sinks nor a pair of disjoint quasi‐kernels. Thus, containing no sinks is not sufficient in general for a digraph to have a pair of disjoint quasi‐kernels. In contrast, we prove that, for several classes of digraphs, the condition of containing no sinks guarantees the existence of a pair of disjoint quasi‐kernels. The classes contain semicomplete multipartite, quasi‐transitive, and locally semicomplete digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:251‐260, 2008

📜 SIMILAR VOLUMES

On the number of quasi-kernels in digrap
On the number of quasi-kernels in digraphs
✍ Gregory Gutin; Khee Meng Koh; Eng Guan Tay; Anders Yeo 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB

## Abstract A vertex set __X__ of a digraph __D__ = (__V, A__) is a __kernel__ if __X__ is independent (i.e., all pairs of distinct vertices of __X__ are non‐adjacent) and for every __v__ ∈ __V__‐__X__ there exists __x__ ∈ __X__ such that __vx__ ∈ __A__. A vertex set __X__ of a digraph __D__ = (__V

Fractional Kernels in Digraphs
Fractional Kernels in Digraphs
✍ Ron Aharoni; Ron Holzman 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

We define a fractional version of the notion of ``kernels'' in digraphs and prove that every clique acyclic digraph (i.e., one in which no clique contains a cycle) has a fractional kernel. Using this we give a short proof of a recent result of Boros and Gurvich (proving a conjecture of Berge and Duc

Arc-disjoint arborescences of digraphs
Arc-disjoint arborescences of digraphs
✍ Cai Mao-cheng 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB

The purpose of this paper is to give a necessary and sufficient condition for a digraph G to contain k arcdisjoint arborescences so that the number rooted at each vertex x of G lies in some prescribed interval which depends on x. A digraph G = (V, E) consists of a vertex set V and an arc set E such

Disjoint Cycles in Eulerian Digraphs and
Disjoint Cycles in Eulerian Digraphs and the Diameter of Interchange Graphs
✍ Richard A. Brualdi; Jian Shen 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 87 KB

denote the set of all m × n {0, 1}-matrices with row sum vector R and column sum vector S. Suppose A(R, S) ] ". The interchange graph G(R, S) of A(R, S) was defined by Brualdi in 1980. It is the graph with all matrices in A(R, S) as its vertices and two matrices are adjacent provided they differ by

On claw-freeM-oriented critical kernel-i
On claw-freeM-oriented critical kernel-imperfect digraphs
✍ Galeana-S�nchez, H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB

A kernel of a digraph D is an independent and dominating set of vertices of D. A chord of a directed cycle C = (0, 1 , . . . , n, 0) is an arc of D not in C with both terminal vertices in C . A diagonal of C is a chord with j # i -1. Meyniel made the conjecture (now know to be false) that if D is a