Abstract
Let be a digraph, possibly infinite, V() and A() will denote the sets of vertices and arcs of , respectively. A subset of V() is said to be a kernel if it is both independent (a vertex in has no successor in ) and absorbing (a vertex not in has a successor in ). An infinite digraph is said to be a finitely critical kernel imperfect digraph if contains no kernel but every finite induced subdigraph of contains a kernel. In this paper we will characterize the infinite kernel perfect digraphs by means of finitely critical imperfect digraphs and strong components of its asymmetric part and then, by using some previous theorems for infinite digraphs, we will deduce several results from the main result. Richardson’s theorem establishes that if is a finite digraph without cycles of odd length, then has a kernel. In this paper we will show a generalization of this theorem for infinite digraphs.
1 Terminology and introduction
For general concepts we refer the reader to [Citation1] and [Citation2]. We will say that two digraphs and are equal, denoted by , if and . A directed walk in a digraph is a sequence () of vertices of such that for each in . We will say that the directed walk is closed if . If for all and such that and , it is called a directed path. A directed cycle is a directed walk such that for all and such that and . If is an infinite digraph, an infinite outward path is a sequence of distinct vertices of such that for each . In this paper we are going to write walk, path, cycle, instead of directed walk, directed path, directed cycle, respectively. Let and be subsets of V(), an arc () of will be called an -arc whenever and .
For the out-neighborhood (respectively in-neighborhood) () (respectively ()) of is { for some } (respectively . A digraph is said to be outwardly finite if is a finite set for every vertex in V().
A digraph is said to be strong if for every pair of vertices and of there is an -path in . A subdigraph of is called a strong component if it is strong and it is maximal with respect to this property. A strong component of is called initial (respectively terminal) if (V()) V() (respectively (V()) V()).
For V() the subdigraph of induced by , denoted by [], has vertex set V([]) = and arc set ([]) = {() () : {, } }. A subset of V() is said to be independent if the only arcs in [] are loops.
An arc () in A() is called asymmetric (resp. symmetric) if () is not in A() (resp. () is in A()). The asymmetric part of , (), is the spanning subdigraph of whose arcs are the asymmetric arcs of . A subdigraph of is asymmetric (symmetric) if all its arcs are asymmetric (symmetric).
A digraph is transitive whenever {(), ()} A() imply that () A(). A digraph is called right-pretransitive (respectively left-pretransitive) whenever {(), ()} A() imply that {(), ()} A() (resp. {(), ()} A() ). A digraph is said to be quasi-transitive if {(), ()} A() imply that {(), ()} A() .
Let be a digraph. A subset of V() is said to be a kernel if it is both independent (a vertex in has no successor in ) and absorbing (a vertex not in has a successor in ). The notion of kernel was introduced in [Citation15] by von Neumann and Morgenstern in the context of Game Theory as a solution for cooperative -player games. If every induced subdigraph of has a kernel, is said to be a kernel perfect digraph. Kernels have been widely studied. A nice survey on the subject is [Citation8]. Chvátal proved in [Citation4] that recognizing digraphs that have a kernel is an NP-complete problem in the context of finite digraphs, so finding sufficient conditions for a digraph to have a kernel or finding large families of digraphs with kernels has been a very prosperous line of investigation explored by many authors.
It is known that: every finite digraph without cycles is a kernel perfect digraph [Citation15], every finite transitive digraph is a kernel perfect digraph [Citation13]; if every cycle of a finite digraph has a symmetric arc, then is a kernel perfect digraph [Citation3]; if is a finite digraph without odd cycles, then is a kernel perfect digraph [Citation16], to name a few. However, this is not the case for infinite digraphs. In [Citation17] R. Rojas-Monroy and I. Villarreal-Valdés considered the digraph which has vertex set and arc set . They observed that is an infinite digraph which is transitive, asymmetric and without cycles (and therefore, without odd cycles) but this digraph is not kernel perfect. Notice that the kernel of a finite induced subdigraph of is its vertex with the largest number, whereas every infinite induced subdigraph does not have a kernel, since there is no maximum of an infinite subset of . It is clear that the behavior of infinite digraphs with respect to kernels is different from the finite case. Some results for the existence of kernels in infinite digraphs are generalizable straightforward from their finite version; in other cases, adding a few new hypotheses will get the work done. An interesting class of digraphs without kernel are the critical kernel imperfect digraphs which are defined as follows: A digraph is said to be critical kernel imperfect if has no kernel but every proper induced subdigraph of has a kernel. A structural property of critical kernel imperfect digraphs, found by Berge and Duchet, is represented in Theorem 1.1.
Theorem 1.1
Berge and Duchet [Citation3]
Let be a finite digraph. If is a critical kernel imperfect digraph, then is strong.
The following theorem is obvious, just take a minimal induced subdigraph with no kernel.
Theorem 1.2
Let be a finite digraph. If has no kernel, then contains an induced subdigraph which is critical kernel imperfect.
R. Rojas-Monroy and I. Villarreal-Valdés showed that Theorem 1.2 is not valid for infinite digraphs if we consider the digraph . They mention that it is not known whether there is an infinite digraph that is critical kernel imperfect but alternatively they give the concept of finitely critical kernel imperfect digraph as follows: an infinite digraph is said to be a finitely critical kernel imperfect digraph if contains no kernel but every finite induced subdigraph of contains a kernel. They proved the following theorem.
Theorem 1.3
[Citation17]
Let be an infinite digraph that contains no kernel. Then contains an induced subdigraph which is either critical kernel imperfect or finitely critical kernel imperfect.
In [Citation6] P. Duchet and H. Meyniel gave a characterization of the infinite kernel perfect digraphs but this characterization was only for outwardly finite digraphs. In this paper our main result consists in the characterization of infinite kernel perfect digraphs by using the concept of finitely critical kernel imperfect digraph. We will prove in Theorem 2.3 that if is a digraph (possibly infinite) and the family of all strong components of (), then is a kernel perfect digraph if and only if (1) [V()] is a kernel perfect digraph for every in and (2) contains no induced subdigraph which is finitely critical kernel imperfect. It is worth to mention that in [Citation12] H. Galeana-Sánchez and V. Neumann-Lara established the finite version of the main result of this paper.
Among the classical results on the theory of kernels we have the following theorem.
Theorem 1.4
Richardson [Citation16]
Let be a finite digraph without odd cycles. Then is a kernel perfect digraph.
Many extensions of Richardson’s theorem have been found over the years. For example, in [Citation5] Duchet proved the following.
Theorem 1.5
Let be a digraph such that every odd cycle possesses at least two symmetric arcs, then is a kernel perfect digraph.
In Theorem 2.7 we will present the infinite version of Theorem 1.5 and as a direct consequence we will deduce Richardson’s theorem.
The following results will be useful in this paper because we will ask similar hypotheses on the induced subdigraph [V()] of for every in .
Theorem 1.6
[Citation6]
Let be an outwardly finite digraph. is a kernel perfect digraph if and only if every finite induced subdigraph has a kernel.
Theorem 1.7
[Citation9]
Let D be a strong digraph, possibly infinite. Then D is bipartite if and only if every cycle has even length.
Theorem 1.8
[Citation10]
Let be a digraph, possibly infinite. Suppose that there exist two subdigraphs of , say and , such that (possibly A( ) A( ) ), where is a right-pretransitive digraph, is a left-pretransitive digraph and contains no infinite outward path for in . Then is a kernel perfect digraph.
Theorem 1.9
[Citation11]
Let be a digraph (possibly infinite) such that (possibly ), where is a quasi-transitive subdigraph of which contains no asymmetric (in ) infinite outward path. If every triangle contained in has at least two symmetric arcs, then is a kernel perfect digraph.
Theorem 1.10
[Citation14]
Every bipartite digraph, finite or infinite, is a kernel perfect digraph.
Remark 1.11
[Citation17]
Let be a nonempty digraph, possibly infinite. Let be the family of all strong subdigraphs of . We define a relation on by if is a subdigraph of . Then () is a nonempty poset and it follows from Zorn’s Lemma that () has a maximal element. Hence has at least one strong component.
Theorem 1.12
[Citation17]
If is a symmetric digraph, finite or infinite, then D is a kernel perfect digraph.
Theorem 1.13
[Citation17]
Let be a digraph, possibly infinite. Suppose that is a right-pretransitive or a left-pretransitive digraph such that every infinite outward path has a symmetric arc. Then is a kernel perfect digraph.
From now on all digraphs are possibly infinite (unless otherwise specified) and the family of all strong components of ().
2 Main results
We will start with some results which are going to be useful.
Proposition 2.1
Let be a digraph. is strong if and only if for every partition of V() into two subsets there exist both a -arc and a -arc in .
Proof
Let {} be a partition of V(), in and in . Since is strong, it follows that there exist a -path and a -path . Let be the least positive integer such that and the least positive integer such that . So, and , which implies that both a -arc and a -arc exist in .
Proceeding by contradiction, suppose that is not strong. Then there exists {} V() such that either there exists no -path or there exists no -path in . Without loss of generality let us suppose there exists no -path in .
Consider the sets = { V() : there exists a -path} and = V(). Notice that {} is a partition of V() such that there exists no -arc in (because ), a contradiction.
Therefore, is strong. □
Lemma 2.2
Let be a digraph. If is a kernel imperfect digraph, then is strong.
Proof
We proceed by contradiction, suppose that () is not strong. It follows from Proposition 2.1 that there exists a partition of V(()) such that either there exists no -arc or there exists no -arc in (). Suppose without loss of generality that there exists no -arc in ().
Since is a kernel imperfect digraph and [] is a proper induced subdigraph of , it follows that [] has a kernel . Consider the subdigraph of induced by the set and call it . Notice that , otherwise is a kernel of which is not possible. Let be a kernel of (there exists because is a proper induced subdigraph of and is a kernel imperfect digraph). Notice that .
We claim that is a kernel of .
We will prove that is an independent set in .
Since and are independent sets in , then it remains to prove that neither there exists -arc nor there exists -arc in .
There exists no -arc in (because by construction of we have that V() () = ). There exists no -arc in , otherwise, if there exist in and in such that () is in A(), then () must be a symmetrical arc (because there exists no -arc in ()), which is not possible because there exists no -arc in .
Therefore, is an independent set in .
Since , it follows that is an absorbent set in .
Therefore, is a kernel of , which is a contradiction.
So, is strong. □
Next, we prove the main result.
Theorem 2.3
is a kernel perfect digraph if and only if (1) is a kernel perfect digraph for every in and (2) contains no induced subdigraph which is finitely critical kernel imperfect.
Proof
Since is a kernel perfect digraph, it follows that (1) [V()] is a kernel perfect digraph for every in (because every induced subdigraph of [V()] is an induced subdigraph of ) and (2) contains no induced subdigraph which is finitely critical kernel imperfect.
Proceeding by contradiction, suppose that is not a kernel perfect digraph. Then there exists a subset of V() such that [] has no kernel.
We claim that [] contains a critical kernel imperfect digraph.
Consider two cases on [].
Case 1.[] is a finite digraph.
Since [] is a finite digraph without kernel, it follows from Theorem 1.2 that [] contains an induced subdigraph which is critical kernel imperfect.
Case 2.[] is an infinite digraph.
In this case we have that [] contains a finite induced subdigraph without kernel (because by hypothesis contains no induced subdigraph which is finitely critical kernel imperfect). So, it follows from Theorem 1.2 that has an induced subdigraph which is critical kernel imperfect.
Let be the induced subdigraph of [] such that is a critical kernel imperfect digraph. Then, it follows from Lemma 2.2 that is strong. Because of that () is a subdigraph of () (because is also an induced subdigraph of ) and it is strong, we have that there exists a strong component of () such that () is a subdigraph of (by Remark 1.11).
Claim. is an induced subdigraph of [V()].
Since V() is a subset of V([V()]), it remains to prove that if {} is a subset of V() such that () A([V()]), then () A().
Let {} be a subset of V() such that () A([V()]). Then () A(), which implies that () A([]) (because {} V() ). So, it follows that () A() (because is an induced subdigraph of [].
Since [V()] is a kernel perfect digraph (by hypothesis) and is an induced subdigraph of [V()], it follows that has a kernel, a contradiction.
Therefore, is a kernel perfect digraph. □
As a direct consequence of Theorem 2.3 we have the following results.
An independent subset of V() is called quasi-kernel if for each vertex in V() there is a path of length at most 2 from to some vertex of . In [Citation7] P.L. Erdős and L. Soukup proved the following.
Theorem 2.4
Let be a digraph. If has finite chromatic number then has a quasi-kernel.
With this result we can deduce that if is a transitive digraph with finite chromatic number then is a kernel perfect digraph (because in the case of transitive digraphs every quasi-kernel in is a kernel). So we get the following Corollary.
Corollary 2.5
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If for every in , [V( )] is a transitive digraph with finite chromatic number, then is a kernel perfect digraph.
Proof
It follows from a combination of Theorems 2.4 and 2.3. □
Corollary 2.6
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If for every in , [V( )] is bipartite, then is a kernel perfect digraph.
Proof
It follows from a combination of Theorems 1.10 and 2.3. □
Theorem 2.7
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If every odd cycle has at least two symmetric arcs, then is a kernel perfect digraph.
Proof
We will first prove that [V()] is a bipartite digraph for every in .
Let be in and suppose that V(), otherwise [V()] already is bipartite.
Consider the following claims.
Claim 1. has no odd cycles.
Since is a subdigraph of () and, by hypothesis, we have that every odd cycle in has at least two symmetric arcs, we conclude that has no odd cycles.
Claim 2. is a bipartite digraph.
Since is strong and it does not have odd cycles, it follows from Theorem 1.7 that is a bipartite digraph.
Let {, } be a partition of V() in two independent sets in .
Claim 3. {, } is a partition of V() in two independent sets in .
Proceeding by contradiction, suppose that is not an independent set in . Then there exists a subset {, } of such that () A(). Since is an independent set in and is a subdigraph of (), it follows that () is a symmetric arc in . On the other hand, since is strong, we have that there exists a -path in , notice that the length of is even. So, () is an odd cycle with exactly one symmetric arc, a contradiction.
Therefore, is an independent set in .
In the same way we can prove that is an independent set in .
Therefore, since [V()] is a bipartite digraph for every in , it follows from Corollary 2.6 that is a kernel perfect digraph. □
Remark 2.8
We cannot omit in Theorem 2.7 the hypothesis “without induced subdigraph which is finitely critical kernel imperfect”. Consider that the digraph (which was mentioned in the introduction) has the following properties:
1. | has no kernel. |
2. | Every finite induced subdigraph of is transitive and therefore it has a kernel. |
3. | Every odd cycle in has at least two symmetric arcs (because has no cycles). |
From 1 and 2 it follows that is a finitely critical kernel imperfect digraph.
Corollary 2.9
Richardson [Citation16]
Let be a finite digraph without odd cycles. Then is a kernel perfect digraph.
Corollary 2.10
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If every odd cycle in [V( )] has at least two symmetric arcs for every in , then is a kernel perfect digraph.
Corollary 2.11
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If [V( )] is an outwardly finite digraph and every finite induced subdigraph of [V( )] has a kernel for every in , then is a kernel perfect digraph.
Proof
It follows from a combination of Theorems 1.6 and 2.3. □
Corollary 2.12
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If for every in , then is a kernel perfect digraph.
Corollary 2.13
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If [V( )] is a right-pretransitive or a left-pretransitive digraph such that every infinite outward path has a symmetric arc for each in , then is a kernel perfect digraph.
Proof
It follows from a combination of Theorems 1.13 and 2.3. □
Corollary 2.14
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. If [V( )] is a transitive digraph such that every infinite outward path has a symmetric arc for each in , then is a kernel perfect digraph.
Proof
It follows from Corollary 2.13. □
Corollary 2.15
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. Suppose that for each in there exist two subdigraphs of [V( )], say and , such that [V( )] = (possibly ), where is a right-pretransitive digraph, is a left-pretransitive digraph and contains no infinite outward path for in . Then is a kernel perfect digraph.
Proof
It follows from a combination of Theorems 1.8 and 2.3. □
Corollary 2.16
Let be a digraph without induced subdigraph which is finitely critical kernel imperfect. Suppose that for each in there exist two subdigraphs of [V( )], say and , such that [V( )] = (possibly ), where is a quasi-transitive which contains no asymmetric (in [V( )]) infinite outward path, and every triangle contained in [V( )] has at least two symmetric arcs. Then is a kernel perfect digraph.
Proof
It follows from a combination of Theorems 1.9 and 2.3. □
Notes
Peer review under responsibility of Kalasalingam University.
References
- J.Bang-JensenG.GutinDigraphs: Theory, Algorithms and Applications2000SpringerLondon
- C.BergeGraphs1989North-HollandAmsterdan
- C.BergeP.DuchetRecent problems and results about kernels in directed graphsDiscrete Math.8619902731
- V. Chvátal, On The Computational Complexity of Finding a Kernel, Report CRM300, Centre de Recherches Mathématiques, Université de Montréal, 1973.
- P.DuchetGraphes noyau-parfaitsAnn. Discrete Math.9198093101
- P.DuchetH.MeynielKernels in directed graphs: a poison gameDiscrete Math.115199327327610.1016/0012-365X(93)90496-G
- P.L.ErdősL.SoukupQuasi-kernels and quasi-sinks in infinite graphsDiscrete Math.309200930403048
- A.S.FraenkelCombinatorial games: selected bibliography with a succinct gourmet introductionElectron J. Combin.2012 DS2. (surveys) http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS2
- H.Galeana-SánchezC.Hernández-CruzOn the existence of (k,l)-kernels in infinite digraphs: a surveyDiscuss. Math. Graph Theory342014431466
- H.Galeana-SánchezR.Rojas-MonroyKernels in pretransitive digraphsDiscrete Math.2752004129136
- H.Galeana-SánchezR.Rojas-MonroyKernels in quasi-transitive digraphsDiscrete Math.306200619691974
- H.Galeana-SánchezV.Neumann-LaraOn kernel-perfect critical digraphsDiscrete Math.591986257265
- D.KönigTheorie Der Endlichen Und Unendlichen Graphen1950Reprinted from Chelsea Publishing CompanyNew York
- V.Neumann-LaraSeminúcleos de una digráficaAn. Inst. Mat.1971 II UNAM
- J.von NeumannO.MorgensternTheory of Games and Economic Behavior1944Princeton University PressPrinceton
- M.RichardsonSolutions of irreflexive relationsAnn. of Math.5831953573590
- R.Rojas-MonroyJ.I.Villarreal-ValdésKernels in infinite digraphsAKCE J. Graphs. Combin.712010103111