BRICS RS-01-7 Gutin et al.: On the Number of Quasi-Kernels in Digraphs BRICS

Basic Research in Computer Science

On the Number of Quasi-Kernels in Digraphs

Gregory Gutin Khee Meng Koh Eng Guan Tay Anders Yeo

BRICS Report Series RS-01-7

ISSN 0909-0878 January 2001 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2001, Gregory Gutin & Khee Meng Koh & Eng Guan

Tay & Anders Yeo. BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/01/7/

On the number of quasi-kernels in digraphs

Gregory Gutin Department of Computer Science

Royal Holloway, University of London

Egham, Surrey, TW20 0EX, UK gutin@dcs.rhbnc.ac.uk

Khee Meng Koh Department of Mathematics

National University of Singapore

119260 Singapore matkohkm@nus.edu.sg

Eng Guan Tay

Mathematics and Mathematics Education Group

Nanyang Technological University 259756 Singapore egtay@nie.edu.sg

Anders Yeo

BRICS, Department of Computer Science University of Aarhus, Ny Munkegade, Building 540

8000 Aarhus C, Denmark yeo@daimi.au.dk

January, 2001

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 1994, 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. We conjecture that every digraph with no sink has a pair of disjoint quasi-kernels and provide some support to this conjecture.

1 Introduction, terminology and notation

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. A digraph T = (V, A) is a tournament if for every pair x, y of distinct vertices in V, either xy ∈ A or yx ∈ A, but not both. A vertex of out-degree zero is called a sink.

While not every digraph has a kernel (e.g., a directed cycle C⃗_{n} has a kernel if and only if n is even), Chvátal and Lovász [2] (see also Chapter 12 in [1]) proved that every digraph has a quasi-kernel. Jacob and Meyniel [3] proved that, if a digraph D has no kernel, then D contains at least three quasi-kernels. While the assertion of Chvátal and Lovász generalizes the fact that every tournament has a 2-serf, i.e., a quasi-kernel of cardinality 1, the Jacob-Meyniel theorem extends the result of Moon [4] that every tournament with no sink has at least three 2-serfs.

While the Jacob-Meyniel theorem provides sufficient conditions for a digraph to have at least three quasi-kernels, in Section 2, 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 (see Theorem 2.6). In particular, we prove that every strong digraph, of order at least three, different from the 4-cycle C⃗_{4} has at least three quasikernels. Note that, in our proofs, we naturally use the Chvátal-Lovász theorem, but not the more powerful Jacob-Meyniel theorem.

In Section 3, we pose a conjecture that every digraph with no sink has a pair of disjoint quasi-kernels. We show that the conjecture is true for every digraph which possesses a quasi-kernel of cardinality at most two and every kernel-perfect digraph, i.e., a digraph for which every induced subdigraph has a kernel. It was proved by von Neumann and Morgenstern [5] that every acyclic digraph is kernel-perfect. Richardson [6] generalized this result by showing that every digraph with no odd cycle is kernel-perfect. Richardson’s theorem was later improved in a number of papers, cf. Section 12.3 in [1].

We use the standard terminology and notation on digraphs as given in [1]. We still provide most of the necessary definitions for the convenience of the reader.

For a digraph D, the vertex (arc) set is denoted by V (D) (A(D)). Let x, y be a pair of vertices in D. If xy ∈ A(D), we say x dominates y, and y is dominated by x, and denote it by x→y. A digraph D is strong if, for every ordered pair x, y of distinct vertices in D, there is a path from x to y. An orientation of a digraph D is an oriented graph obtained from D by deleting exactly one arc from each 2-cycle in D. A biorientation of D is a digraph, which is a subdigraph of D and superdigraph of an orientation of D. The closed in-neighbourhood (closed out-neighbourhood) of a set X of vertices of a digraph D = (V, A) is defined as follows.

N_{D}^{−}[X] = X∪{y ∈ V : ∃x ∈ X, y→x} (N_{D}^{+}[X] = X∪{y ∈ V : ∃x ∈ X, x→y}).

For disjoint subsets X and Y of V (D), let X × Y = {xy : x ∈ X, y ∈ Y }, (X, Y)_{D} = (X × Y) ∩ A(D); D[X] is the subdigraph of D induced by X. If the digraph under consideration is clear from the context, then we will omit the subscript D.

2 Digraphs with exactly one and two quasi-kernels

We start with the following:

Lemma 2.1 Let x be a vertex in a digraph D. If x is a non-sink, then D has a quasi-kernel not including x.

Proof: Let y ∈ N^{+}[x] − {x} be arbitrary. If N^{−}[y] = V (D), then y is the required quasi-kernel. If N^{−}[y] ≠ V (D), let Q′ be a quasi-kernel in D − N^{−}[y]. If y dominates a vertex in Q′, then Q′ is a quasi-kernel in D, which does not contain x. If y does not dominate a vertex in Q′, then Q′ ∪ {y} is a quasi-kernel in D, which does not include x. □

The following is an easy characterization of digraphs with merely one quasi-kernel.

Theorem 2.2 A digraph D has only one quasi-kernel if and only if D has a sink and every non-sink of D dominates a sink of D. If a digraph D has only one quasi-kernel Q, then Q is a kernel and consists of the sinks of D.

Proof: Assume that D has a sink and every non-sink of D dominates a sink of D. Let S be the set of sinks in D. To see that S is a unique quasi-kernel of D, it is enough to observe that every sink must be in a quasi-kernel.

Let D have only one quasi-kernel Q. To see that Q is the set of sinks in D, observe that Q contains all sinks in D and, by Lemma 2.1, Q does not have non-sinks. If x is a non-sink and x does not dominate a vertex in Q, then Q ∪ {x} is another quasi-kernel of D, a contradiction. Thus, we have proved that D has a sink and every non-sink of D dominates a sink of D. □

In view of Theorem 2.2, the following assertion is a strengthening of the Jacob-Meyniel theorem for the case of digraphs with no sinks.

Theorem 2.3 Let D be a digraph with no sink. Then D has precisely two quasi-kernels if and only if D has an induced 4-cycle or 2-cycle, C, such that no vertex of C dominates a vertex in D − V (C) and every vertex in D − V (C) dominates at least two adjacent vertices in C.

To prove Theorem 2.3, we will extensively use the following:

Lemma 2.4 Let a digraph D have exactly two quasi-kernels, R and Q. Then the following claims hold:

(i) If a vertex x in R dominates some vertex y such that V (D) ≠ N^{−}[y], then Q − y is the only quasi-kernel in D − N^{−}[y];

(ii) {R, Q} is the set of quasi-kernels of every biorientation of D, in which both R and Q contain non-sinks.

Proof: Let R_{1}, R_{2}, …, R_{k} be the quasi-kernels in D−N^{−}[y]. Then R′_{1}, R′_{2}, …, R′_{k} are quasi-kernels in D, where R′_{i} = R_{i} if (y, R_{i}) ≠ ∅ and R′_{i} = R_{i} ∪ {y}, otherwise, i = 1, 2, …, k. Since D has only two quasi-kernels, k ≤ 2. Since x ∈ N^{−}[y] and x ∈ R, we conclude that R − y is not a quasi-kernel in D − N^{−}[y]. By the Chvátal- Lovász theorem, every digraph has a quasikernel, so Q − y is the unique quasi-kernel in D − N^{−}[y].

Let D′ be a biorientation of D, in which both R and Q contain nonsinks. Clearly, every quasi-kernel in D′ is a quasi-kernel in D. However, by Theorem 2.2, neither R nor Q can be the only quasi-kernel in D′. Thus {R, Q} is the set of quasi-kernels of D′. □

Proof of Theorem 2.3: We first show that, if D has precisely two quasikernels, then D has the above-described structure. We will prove this assertion by induction on |V (D)|. The assertion is clearly true when |V (D)| ≤ 2, so we may assume that it is true for all digraphs, D^{∗}, with |V (D^{∗})| < |V (D)|. Let Q_{1} and Q_{2} be the only two quasi-kernels in D. Note that by Lemma 2.1, Q_{1} and Q_{2} must be disjoint (if x ∈ Q_{1} ∩ Q_{2} then use Lemma 2.1 for x). We now prove the following claims.

Claim A: If (Q_{i}, Q_{j}) ≠ ∅ ({i, j} = {1, 2}), then for every w ∈ Q_{i}, (w, Q_{j}) ≠ ∅.

Proof of Claim A: Let xy ∈ (Q_{i}, Q_{j}) and let w be a vertex in Q_{i} which has no arc into Q_{j}. By Lemma 2.4(i), Q_{j} − y is the unique kernel in D − N^{−}[y] and, thus, by Theorem 2.2, we must have an arc from w to Q_{j} − y since w ∈ V (D) − N^{−}[y], a contradiction.

Claim B: Both (Q_{1}, Q_{2}) and (Q_{2}, Q_{1}) are non-empty.

Proof of Claim B: Clearly Q_{1} ∪ Q_{2} is not an independent set, as then it would be a quasi-kernel. Hence, without loss of generality we may assume that (Q_{1}, Q_{2}) ≠ ∅. Suppose that (Q_{2}, Q_{1}) = ∅. Since Q_{1} is a quasi-kernel, there exists a 2-path from any given x ∈ Q_{2} to Q_{1}, say xzy (z ∉ Q_{1} ∪ Q_{2} and y ∈ Q_{1}).

We now show that every vertex in Q_{2} must dominate z. Suppose that this is not the case, and let w be a vertex not dominating z. By Lemma 2.4, Q_{1} is the only quasi-kernel in D − N^{−}[z]. However, by Theorem 2.2, this is a contradiction against the fact that w dominates no vertex in Q_{1} (w ∈ V (D) − N^{−}[z]). Thus, Q_{2} ⊆ N^{−}[z].

Let D′ be any orientation of D for which (z, Q_{2})_{D′} = ∅, and let ab be an arc in (Q_{1}, Q_{2})_{D′}. Since z ∈ V (D′) − N_{D′}^{−}[b], we have V (D′) ≠ N_{D′}^{−}[b]. By Lemma 2.4, Q_{2} − b is the only quasi-kernel in D′ − N_{D′}^{−}[b]. By Theorem 2.2, Q_{2} − b is a kernel in V (D′) − N_{D′}^{−}[b]. However, Q_{2} − b is not a kernel in D′ − N_{D′}^{−}[b] as z dominates no vertex in Q_{2} − b, a contradiction.

Claim C: Let {a, b} be a set of two distinct vertices from Q_{1} and let {c, d} be a set of two distinct vertices from Q_{2}. Then we cannot have both a→c and d→b.

Proof of Claim C: Assume that a→c and d→b. Suppose first that c↛b. By Lemma 2.4, Q_{1} − b is the only quasi-kernel in V (D) − N^{−}[b]. However, since the arc ac ∈ D − N^{−}[b] we see that Q_{1} − b contains a nonsink in V (D) − N^{−}[b] in contradiction with Theorem 2.2. Suppose now that c→b, and let D′ equal D − bc (if bc ∉ D, then D′ = D). By Lemma 2.4, Q_{2} − c is the only quasi-kernel in V (D′) − N^{−}[c]. However, since the arc db ∈ D′ − N_{D′}^{−}[c] we see that Q_{2} − c contains a non-sink in contradiction with Theorem 2.2.

Claim D: Either D[Q_{1} ∪ Q_{2}] is a 2-cycle or D[Q_{1} ∪ Q_{2}] contains an induced 4-cycle.

Proof of Claim D: If either Q_{1} or Q_{2} has only one vertex, then without loss of generality we may assume that |Q_{1}| = 1. If |Q_{2}| = 1 then by Claim B, D[Q_{1} ∪ Q_{2}] is a 2-cycle, so assume that |Q_{2}| ≥ 2. Let Q_{1} = {x} and observe that by Claims A and B there exists a pair a, b of distinct vertices in Q_{2} such that ax, xb ∈ A(D). Let D′ be any orientation of D with ax, xb ∈ A(D′). By Lemma 2.4, Q_{1} − x is the only quasi-kernel in the non-empty digraph D′ − N_{D′}^{−}[x], which contradicts the fact that Q_{1} = {x}.

Therefore, we may now assume that both Q_{1} and Q_{2} have cardinality at least two. By Claim B, there exists an arc x_{2}x_{1} in (Q_{2}, Q_{1})_{D}. Let y_{1} ∈ Q_{1} − {x_{1}} be arbitrary, and observe that (y_{1}, Q_{2}) ≠ ∅, by Claims A and B. By Claim C, y_{1}x_{2} ∈ (y_{1}, Q_{2}). Let y_{2} ∈ Q_{2} − {x_{2}} be arbitrary. Analogously, we have y_{2}y_{1} ∈ A(D). Finally, Claims A and C imply that x_{1}y_{2} ∈ A(D). Therefore, C = x_{2}x_{1}y_{2}y_{1}x_{2} is a 4-cycle. Observe that C is an induced 4-cycle, by Claim C and the fact that {x_{1}, y_{1}} and {x_{2}, y_{2}} are independent sets (they are subsets of quasi-kernels).

Claim E: If abcda is a 4-cycle such that {a, c} ⊆ Q_{1} and {b, d} ⊆ Q_{2}, then there is no arc from {a, b, c, d} to any vertex in D − {a, b, c, d}.

Proof of Claim E: Assume that the claim is false and that there exists a vertex z ∈ V (D) − {a, b, c, d} such that there is an arc from {a, b, c, d} to z. Without loss of generality, assume that az ∈ A(D), and consider the following two cases.

Case 1: z→c. Let D′ be any orientation of D with zc, az ∈ A(D′). By Lemma 2.4, Q_{2} − z is the only quasi-kernel in D′ − N_{D′}^{−}[z]. However, the existence of the arc bc ∈ D′ contradicts Theorem 2.2.

Case 2: z↛c. By Lemma 2.4(i), Q_{1} −c is the only quasi-kernel in N_{D}^{−}[c]. However, the existence of the arc az ∈ D − N^{−}[c] contradicts Theorem 2.2.

Claim F: If abcda is a 4-cycle such that {a, c} ⊆ Q_{1} and {b, d} ⊆ Q_{2}, then every vertex in D−{a, b, c, d} dominates two adjacent vertices on abcda.

Proof of Claim F: Let x ∈ V (D) − {a, b, c, d} be arbitrary. If x has no arc into {a, b, c, d}, then consider the digraph D^{∗} = D − N^{−}[x]. Clearly, Q_{1} − N^{−}[x] and Q_{2} − N^{−}[x] are distinct quasi-kernels in D^{∗}; D^{∗} cannot have another quasi-kernel as D has only two quasi-kernels. Therefore there are exactly two quasi-kernels in D^{∗}, and by our induction hypothesis, these quasi-kernels are precisely {a, c} and {b, d}. Observe that, by Claim E, x is adjacent to no vertex from the set {a, b, c, d}. However, this means that both {x, a, c} and {x, b, d} are quasi-kernels in D, contradicting the fact that Q_{1} and Q_{2} are disjoint. Therefore, x must have an arc into {a, b, c, d}. Observe that since x is arbitrary, this implies that {a, c} and {b, d} are quasi-kernels in D.

Without loss of generality, assume that x→a in D. Suppose also that x↛b and x↛d, as otherwise we would be done. However, these assumptions imply that {x, b, d} also is a quasi-kernel, along with {a, c} and {b, d}, a contradiction.

Claim G: If C = D[Q_{1} ∪Q_{2}] is a 2-cycle, then no vertex of C dominates a vertex in D −V (C) and every vertex in D −V (C) dominates both vertices in C.

Proof of Claim G: Let C = xyx. Assume there exists an arc xz, z ≠ y. Consider an orientation, D′, of D such that D′ − N_{D′}^{−}[x] contains z and does not contain y. On one hand, D′ has no quasi-kernels other than {x} and {y}; on the other hand, either Q or Q ∪ {x} is a quasi-kernel in D′, where Q is a quasi-kernel in D′ − N_{D′}^{−}[x]. We have arrived at a contradiction. Therefore (V (C), V (D) − V (C)) = ∅. Furthermore, every vertex v ∈ V (D) − V (C) must dominate both vertices on C since otherwise there would be a quasikernel containing v.

Claims D,E, F and G prove the assertion on the structure of D.

Now assume that D has the structure described in this theorem, and C is the cycle in D. If C is a 2-cycle, then it is easy to see that each of the two vertices on C is a quasi-kernel (and kernel) in D, and that there are no other quasi-kernels in D. So now assume that C = abcda is an induced 4-cycle in D. Observe that {a, c} and {b, d} are quasi-kernels in D. Since ({a, b, c, d}, V (D) − {a, b, c, d}) = ∅, any quasi-kernel in D must contain a vertex, x, in C. Since the successor x^{+} of x in C has to be able to reach the quasi-kernel with a path of length at most two, (x^{+})^{+} must also belong to the quasi-kernel. Since all other vertices are adjacent to one of these vertices, the only quasi-kernels are {a, c} and {b, d}. □

As corollaries we obtain the following two theorems.

Theorem 2.5 A strong digraph D of order at least three has at least three quasi-kernels, unless D is C⃗_{4}.

Proof: Immediate from the previous theorems, Theorems 2.2 and 2.3. □

Theorem 2.6 Let D be a digraph, S the set of sinks in D, R the set of vertices that have an arc into S, and H = D − S − R. Then D has precisely two quasi-kernels, if and only if one of the following holds:

(a) There is a 2-cycle C in H such that at most one of the vertices in C has an arc into R, no vertex of C dominates a vertex in H − V (C), and every vertex in H − V (C) dominates both vertices in C.

(b) There is an induced 4-cycle, C, in H such that no vertex of C dominates a vertex in D − V (C) and every vertex in H − V (C) dominates two adjacent vertices in C.

(c) The digraph H has at least two vertices. There is a vertex x in H such that no vertex of H is dominated by x, all the vertices of H−x dominate x, i.e., (V (H) − {x}, x) = (V (H) − {x}) × {x}, and there is a kernel Q in H − x, consisting only of sinks in H − x. Moreover, there is no arc from Q to R.

(d) The digraph H consists of a single vertex.

Proof: We first show that, if D has precisely two quasi-kernels, then D has the above-described structure. Let D be a digraph with exactly two quasi-kernels. If D has no sinks, then by Theorem 2.3, D has the structure described in part (a) or (b) with R ∪ S = ∅. Hence, we may assume that D contains some sinks, and let S, R and H be as defined in the formulation of this theorem. Let us first prove that H has at most one sink.

Suppose that there are at least two sinks in H. Let x and y be two distinct sinks in H. Note that both x and y have arcs into R, since otherwise they would belong to S or R. Let Q_{1} be a quasi-kernel in H, Q_{2} a quasikernel in H − x, and Q_{3} a quasi-kernel in H − y. Since {x, y} ⊆ Q_{1}, {x, y} ∩ Q_{2} = {y} and {x, y} ∩ Q_{3} = {x} we see that Q_{1} ∪ S, Q_{2} ∪ S and Q_{3} ∪ S are 3 different quasi-kernels in D, a contradiction. Hence, H has at most one sink.

Suppose that there is exactly one sink x in H. Since the case of H having exactly one vertex is trivial, we may assume that H contains at least two vertices. Let Q_{1} be a quasi-kernel in H, and let Q_{2} be a quasi-kernel in H−x. Note that S∪Q_{1} and S∪Q_{2} are different quasi-kernels in D (as x ∈ Q_{1} and x has an arc into R). Therefore, Q_{2} must be the unique quasi-kernel in H − x, and, by Theorem 2.2, Q_{2} is a kernel in H−x consisting only of sinks in H−x. Since x is the only sink in H, every vertex in Q_{2} dominates x. Therefore, {x} is a quasi-kernel in H. Since x must be the unique quasi-kernel in H and x is a sink, we must have (V (H) − {x}, x) = (V (H) − {x}) × {x}. Thus, S ∪ {x} and S ∪ Q_{2} are quasi-kernels in D. If there is a vertex w ∈ Q_{2} which dominates a vertex in R, then let Q_{3} be a quasi-kernel in H − w − x, and observe that Q_{3} ∪ S is a third quasi-kernel, a contradiction. Therefore, D has the structure described in part (c).

Suppose now that H has no sink. (Since D has more than one quasikernel, H is non-empty.) By Theorem 2.2, there are at least two quasikernels, Q_{1} and Q_{2}, in H. If Q is a quasi-kernel in H, then S ∪ Q is a quasi-kernel in D. Hence, Q_{1} and Q_{2} are the only quasi-kernels in H, and, thus, the structure of H is provided by Theorem 2.3. Let C be the 2-cycle or induced 4-cycle given in Theorem 2.3.

If C is a 2-cycle, xyx, then, by Theorem 2.3, to show that D has the structure described in part (a) it suffices to prove that at most one of the vertices x and y has an arc into R. Assume that both x and y have arcs into R. Let Q_{3} be a quasi-kernel in H − x − y, if V (H) ≠ {x, y}, and the empty set, otherwise. However, S ∪ x, S ∪ y and S ∪ Q_{3} are three different quasi-kernels in D, a contradiction.

If C is an induced 4-cycle, abcda, then, by Theorem 2.3, to show that D has the structure described in part (b) it suffices to prove that no vertex in V (C) dominates a vertex in R. Without loss of generality, assume that a dominates a vertex in R. By Lemma 2.1, there exists a quasi-kernel, Q, in H − a, which does not contain b, as b is not a sink in H − a. However, Q ∪ S, {a, c} ∪ S and {b, d} ∪ S are three different quasi-kernels in D, a contradiction.

This proves that, if D has exactly two quasi-kernels, then D has the structure described in the formulation of this theorem. If D has the structure provided in part (a), (b), (c) or (d), then it is not too difficult to check that there are exactly two quasi-kernels in D. □

3 Disjoint quasi-kernels

If a digraph D has a sink x, then every quasi-kernel in D must contain x. Hence, a digraph with sinks has no disjoint quasi-kernels. However, we suspect that the following holds.

Conjecture 3.1 Every digraph with no sink has a pair of disjoint quasikernels.

By Lemma 2.1, this conjecture holds for digraphs with exactly two quasikernels: see the first paragraph in the proof of Theorem 2.3. We will show that the conjecture is also true for every digraph which possesses a quasikernel of cardinality at most two and every kernel-perfect digraph. We recall that a digraph D is kernel-perfect if every induced subdigraph of D has a kernel.

We start with the following useful lemma.

Lemma 3.2 Let D be a digraph and let Y be a set of vertices in D such that D[Y] is kernel-perfect. Then there exists a quasi-kernel, Q, in D, such that Q ⊆ V (D) − (N^{−}[Y] − Y).

Proof: Let H = D − N^{−}[Y] and let Q_{1} be a quasi-kernel in H (if H = ∅ then Q_{1} = ∅). Let Y′ contain all vertices from Y, which have no arc into Q_{1}. Since D[Y] is kernel-perfect, there is a kernel, K′, in D[Y′]. We claim that Q = Q_{1} ∪ K′ is the desired quasi-kernel in D.

Clearly, Q is an independent set as Q_{1} and K′ are independent sets, there is no arc from K′ to Q_{1} (by the definition of Y′) and there is no arc from Q_{1} to K′ (by the definition of H). By the definition of Q_{1}, every vertex in H can reach Q with a path of length at most 2. Observe that every vertex in Y − K′ dominates a vertex in Q (each y ∈ Y either has an arc into Q_{1} or is a vertex in Y′ and has an arc into K′ or is in K′). Therefore, every vertex in N^{−}(Y) can reach Q with a path of length at most 2. □

Corollary 3.3 Every kernel-perfect digraph with no sink has a pair of disjoint quasi-kernels.

Proof: Let D be a kernel-perfect digraph with no sink, K a kernel in D, Y = N^{+}[K] − K. Observe that K ⊆ N^{−}[Y] − Y. Hence, by Lemma 3.2, D has a quasi-kernel disjoint from K. □

Corollary 3.4 Let D be a digraph, and let S = {x, y} be a set of distinct vertices in D such that N^{+}[x]−S ≠ ∅ and N^{+}[y]−S ≠ ∅. Then there exists a quasi-kernel in D, which is disjoint from S.

Proof: Let u ∈ N^{+}[x]−S and v ∈ N^{+}[y]−S be arbitrary (possibly u = v). Since D[{u, v}] is obviously kernel-perfect and S ⊆ N^{−}[{u, v}] − {u, v}, the desired result follows from Lemma 3.2. □

It follows from Corollary 3.4 that Conjecture 3.1 is true for every digraph with a quasi-kernel of cardinality at most 2.

Corollary 3.4 cannot be improved to sets of size 3, by the following example. Let V (D) = {x_{1}, x_{2}, x_{3}, y_{1}, y_{2}, y_{3}, z_{1}, z_{2}, z_{3}} and let the arc set of D contain the 3-cycles x_{i}y_{i}z_{i}x_{i} for i = 1, 2, 3, z_{1}z_{2}z_{3}z_{1} and y_{1}y_{2}y_{3}y_{1} as well as the arcs {z_{1}y_{2}, z_{1}y_{3}, z_{2}y_{1}, z_{2}y_{3}, z_{3}y_{1}, z_{3}y_{2}}. By the definition of D, X = {x_{1}, x_{2}, x_{3}} is a quasi-kernel of size 3. To see that X intersects any other quasi-kernel in D, observe that every pair of vertices in D − X is adjacent and none of the vertices in D − X is a quasi-kernel (for example, the shortest path from x_{2} to y_{1} is of length 3). At the same time, {x_{1}, y_{3}} and {y_{1}, x_{2}} are disjoint quasi-kernels.

Acknowledgements

We are grateful to David Cohen, Royal Holloway, University of London, for his useful comments and suggestions. Parts of this work were done when GG was visiting the Department of Mathematics, National University of Singapore and AY was visiting the Department of Computer Science, Royal Holloway, University of London. The hospitality and financial support of the respective departments are very much appreciated.

References

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2000.

[2] V. Chvátal and L. Lovász, Every directed graph has a semi-kernel, Lecture Notes in Math. 411 (1994) 175, Springer, Berlin.

[3] H. Jacob and H. Meyniel, About quasi-kernels in a digraph, Discrete Math. 154 (1996) 279–280.

[4] J.W. Moon, Solution to problem 463, Math. Mag. 35 (1962) 189.

[5] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behaviour, Princeton University Press, Princeton, 1944.

[6] M. Richardson, Solution of irreflective relations, Ann. Math. 58 (1953) 573–580.

Recent BRICS Report Series Publications

RS-01-7 Gregory Gutin, Khee Meng Koh, Eng Guan Tay, and Anders Yeo. On the Number of Quasi-Kernels in Digraphs. January 2001. 11 pp.

RS-01-6 Gregory Gutin, Anders Yeo, and Alexey Zverovich. Traveling Salesman Should not be Greedy: Domination Analysis of Greedy-Type Heuristics for the TSP. January 2001. 7 pp.

RS-01-5 Thomas S. Hune, Judi Romijn, Mariëlle Stoelinga, and Frits W. Vaandrager. Linear Parametric Model Checking of Timed Automata. January 2001. 44 pp. To appear in Tools and Algorithms for The Construction and Analysis of Systems: 7th International Conference, TACAS ’01 Proceedings, LNCS, 2001.

RS-01-4 Gerd Behrmann, Ansgar Fehnker, Thomas S. Hune, Kim G. Larsen, Paul Pettersson, and Judi Romijn. Efficient Guiding Towards Cost-Optimality in Uppaal. January 2001. 21 pp. To appear in Tools and Algorithms for The Construction and Analysis of Systems: 7th International Conference, TACAS ’01 Proceedings, LNCS, 2001.

RS-01-3 Gerd Behrmann, Ansgar Fehnker, Thomas S. Hune, Kim G. Larsen, Paul Pettersson, Judi Romijn, and Frits W. Vaandrager. Minimum-Cost Reachability for Priced Timed Automata. January 2001. 22 pp. To appear in Hybrid Systems: Computation and Control, 2001.

RS-01-2 Rasmus Pagh and Jakob Pagter. Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting. January 2001. ii+20 pp.

RS-01-1 Gerth Stølting Brodal, Anna Östlin, and Christian N. S. Pedersen. The Complexity of Constructing Evolutionary Trees Using Experiments. 2001.

RS-00-52 Claude Crépeau, Frédéric Légaré, and Louis Salvail. How to Convert a Flavor of Quantum Bit Commitment. December 2000. 24 pp. To appear in Advances in Cryptology: International Conference on the Theory and Application of Cryptographic Techniques, EUROCRYPT ’01 Proceedings, LNCS, 2001.