Article in press
Authors:
Title:
Poison Game for semikernels of arbitrary digraphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-06-28 , Revised: 2024-09-10 , Accepted: 2024-09-10 , Available online: 2024-09-25 , https://doi.org/10.7151/dmgt.2562
Abstract:
A modified version of Duchet and Meyniel's Poison Game is presented, which can
be played on arbitrary digraphs without sinks. Player $A$ has a winning
strategy if and only if the graph has a semikernel; the winning condition for
this player is that the game is infinite. Even for the uncountable graphs, it
suffices to consider games with up to $\omega$ steps.
Keywords:
infinite digraphs, kernels, semikernels
References:
- C. Berge and P. Duchet, Perfect graphs and kernels, Bull. Inst. Math. Acad. Sin. 16 (1988) 263–274.
- C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27–31.
https://doi.org/10.1016/0012-365X(90)90346-J - M. Blidia, A parity digraph has a kernel, Combinatorica 6(1) (1986) 23–27.
https://doi.org/10.1007/BF02579405 - E. Boros and V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete Math. 306 (2006) 2336–2354.
https://doi.org/10.1016/j.disc.2005.12.031 - M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. of Math. (2) 164 (2006) 51–229.
https://doi.org/10.4007/annals.2006.164.51 - R.T. Cook, Patterns of paradox, J. Symb. Log. 69 (2004) 767–774.
https://doi.org/10.2178/jsl/1096901765 - P. Duchet and H. Meyniel, Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientés, Discrete Math. 43 (1983) 21–27.
https://doi.org/10.1016/0012-365X(83)90017-1 - P. Duchet and H. Meyniel, Kernels in directed graphs: a poison game, Discrete Math. 115 (1993) 273–276.
https://doi.org/10.1016/0012-365X(93)90496-G - H. Galeana-Sánchez and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67–76.
https://doi.org/10.1016/0012-365X(84)90131-6 - V. Neumann-Lara, Seminúcleos de una Digráfica, Technical Report (Anales del Instituto de Matemáticas II, Universidad Nacional Autónoma México, 1971).
- M. Richardson, Solutions of irreflexive relations, Ann. of Math. (2) 58 (1953) 573–590.
https://doi.org/10.2307/1969755 - R. Sánchez-López, Infinite kernel perfect digraphs, AKCE Int. J. Graphs Comb. 14 (2017) 165–171.
https://doi.org/10.1016/j.akcej.2017.02.005 - J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, 1944).
- M. Walicki, Resolving infinitary paradoxes, J. Symb. Log. 82 (2017) 709–723.
https://doi.org/10.1017/jsl.2016.18 - M. Walicki, Kernels of digraphs with finitely many ends, Discrete Math. 342 (2019) 473–486.
https://doi.org/10.1016/j.disc.2018.10.026
Close