𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the number of quasi-kernels in digraphs

✍ Scribed by Gregory Gutin; Khee Meng Koh; Eng Guan Tay; Anders Yeo

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
89 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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, A), is a quasi‐kernel if X is independent and for every v ∈ V‐X there exist w ∈ V‐X, x ∈ X such that either vx ∈ A or vw, wx ∈ A. In 1974, Chvátal and Lovász proved that every digraph has a quasi‐kernel. In 1996, Jacob and Meyniel proved that if a digraph D has no kernel, then D contains at least three quasi‐kernels. We characterize digraphs with exactly one and two quasi‐kernels, and, thus, provide necessary and sufficient conditions for a digraph to have at least three quasi‐kernels. In particular, we prove that every strong digraph of order at least three, which is not a 4‐cycle, has at least three quasi‐kernels. © 2004 Wiley Periodicals, Inc.

📜 SIMILAR VOLUMES

Disjoint quasi-kernels in digraphs
Disjoint quasi-kernels in digraphs
✍ Scott Heard; Jing Huang 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## 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 o

The circular chromatic numbers of planar
The circular chromatic numbers of planar digraphs
✍ Chin-Ann Soh 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 1 views

## Abstract The circular chromatic number is a refinement of the chromatic number of a graph. It has been established in [3,6,7] that there exists planar graphs with circular chromatic number __r__ if and only if __r__ is a rational in the set {1} ∪ [2,4]. Recently, Mohar, in [1,2] has extended the

The circular chromatic number of a digra
The circular chromatic number of a digraph
✍ Drago Bokal; Gas̆per Fijavz; Martin Juvan; P. Mark Kayll; Bojan Mohar 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

## Abstract We introduce the circular chromatic number χ~__c__~ of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directe

On the Capacity of Digraphs
On the Capacity of Digraphs
✍ Noga Alon 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 76 KB

For a digraph G = (V, E) let w(G n ) denote the maximum possible cardinality of a subset S of V n in which for every ordered pair It is also shown that for every n there is a tournament T on 2n vertices whose capacity is at least √ n, whereas the maximum number of vertices in a transitive subtourna

The number of vertices of degree k in a
The number of vertices of degree k in a minimally k-edge-connected digraph
✍ Yuan Xu-dong; Kang Liying; Cai Mao-cheng 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 2 views

Let k be a positive integer, and D = (V (D), E(D)) be a minimally k-edge-connected simple digraph. We denote the outdegree and indegree of x ∈ V (D) by δ D (x) and ρ D (x), respectively. Let u + (D) denote the number of vertices W. Mader asked the following question in [Mader, in Paul Erdös is Eigh