×

On kernels of graphs and solutions of games: A synopsis based on relations and fixpoints. (English) Zbl 0554.05032

Authors’ abstract: ”We aim at a uniform approach to results concerning the existence of kernels of graphs and introduce new results in the bipartite case. The Galois connection based on the function which assigns to a vertex set the set of its nonpredecessors is investigated using a special fixpoint theorem; it is illustrated by the notions of retardation and expansiveness. The related topic of solutions of games is mentioned, and an analysis of some chess endings is included as an application. The paper contains an extended bibliography.”
Reviewer: P.Avery

MSC:

05C20 Directed graphs (digraphs), tournaments
03E20 Other classical set theory (including functions, relations, and set algebra)
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68R10 Graph theory (including graph drawing) in computer science
91A80 Applications of game theory
91A05 2-person games
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anciaux-Mundeleer, M.; Hansen, P., On kernels in strongly connected graphs, Networks, 7, 263, (1977) · Zbl 0364.05028
[2] Aumann, Georg, Über autogene folgen und die konstruktion des kerns eines graphen, Bayer. Akad. Wiss. Math.-Natur. Kl.S.-B., 1966, (1966) · Zbl 0314.90101
[3] Behzad, M.; Harary, F., Which directed graphs have a solution?, Math. Slovaca, 27, 37, (1977) · Zbl 0368.05027
[4] Berge, Claude, Sur l’inversion des transformateurs, C. R. Acad. Sci. Paris, 232, 134, (1951) · Zbl 0042.05401
[5] Berge, C., Théorie générale des jeux à n personnes, 114, (1957) · Zbl 0082.34702
[6] Berge, C., Nouvelles extensions du noyau d’un graphe et ses applications en théorie des jeux, Publ. Économétriques, 6, 6, (1973) · Zbl 0257.05113
[7] Blair, Charles; Roth, AlvinE., An extension and simple proof of a constrained lattice fixed point theorem, Algebra Universalis, 9, 131, (1979) · Zbl 0421.06005
[8] Borowiecki, Mieczysław, On the graphs with minimaximal kernels, Prace Nauk. Inst. Mat. Politech. Wrocław. No. 17 Ser. Stud. i Materiały, 3, (1977) · Zbl 0398.05064
[9] Bouton, CharlesL., Nim, a game with a complete mathematical theory, Ann. of Math. (2), 3, 35, (190102) · JFM 32.0225.02
[10] Chao, C.-Y., On a problem of C. berge, Proc. Amer. Math. Soc., 14, 80, (1963) · Zbl 0114.40002
[11] Chvátal, V.; Lovász, L.; Berge, C.; Ray-Chauduri, D., Every directed graph has a semi-kernel, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), (1974), Springer, Berlin · Zbl 0297.05116
[12] Clarke, M. R. B., Advances in computer chess 1, (1977) · Zbl 0455.68045
[13] Coxeter, H. S. M., The Golden section, phyllotaxis, and Wythoff’s game, Scripta Math., 19, 135, (1953) · Zbl 0053.00702
[14] Duchet, P., Graphes noyau-parfaits, Ann. Discrete Math., 9, 93, (1980) · Zbl 0462.05033
[15] Duchet, P., Two problems in kernel theory, Ann. Discrete Math., 9, 302, (1980)
[16] Duchet, Pierre; Meyniel, Henri, A note on kernel-critical graphs, Discrete Math., 33, 103, (1981) · Zbl 0456.05032 · doi:10.1016/0012-365X(81)90264-8
[17] Duchet, Pierre; Meyniel, Henri, Une généralisation du théorème de Richardson sur l’existence de noyaux dans LES graphes orientés, Discrete Math., 43, 21, (1983) · Zbl 0502.05027 · doi:10.1016/0012-365X(83)90017-1
[18] Euwe, M., Mengentheoretische betrachtungen über fiber das schachspiel, Proc. Section of Sciences. Koninklijke Akad. van Wetensch., 32, 633, (1929) · JFM 55.0057.02
[19] Fraenkel, AviezriS., Planar kernel and Grundy with \(d≤ 3, d\sb{{\rm out}}≤ 2, d\sb{{\rm i}{\rm n}}≤ 2\) are NP-complete, Discrete Appl. Math., 3, 257, (1981) · Zbl 0493.68040 · doi:10.1016/0166-218X(81)90003-2
[20] Galeana-Sánchez, Hortensia, A counterexample to a conjecture of meyniel on kernel-perfect graphs, Discrete Math., 41, 105, (1982) · Zbl 0484.05035
[21] Grundy, P. M.; Smith, C. A. B., Disjunctive games with the last player losing, Proc. Cambridge Philos. Soc., 52, 527, (1956) · Zbl 0074.34504
[22] Guy, RichardK.; Smith, CedricA. B., The {\it G}-values of various games, Proc. Cambridge Philos. Soc., 52, 514, (1956) · Zbl 0074.34503
[23] Reviews MR 58 33000, 80c: 90159
[24] Harary, F.; Richardson, M., A matrix algorithm for solutions and {\it r}-bases of a finite irreflexive relation, Naval Res. Logist. Quart., 6, 307, (1959)
[25] Kalmár, L., Zur theorie der abstrakten spiele, Acta Sci. Math. (Szeged), 4, 65, (192829) · JFM 54.0096.01
[26] Knaster, B., Un théorème sur LES fonctions d’ensembles, Ann. Société Polonaise de Mathématique, 6, 133, (1927) · JFM 54.0091.04
[27] König, D., Über eine schlussweise aus dem endlichen ins unendliche, Acta Sci. Math. (Szeged), 3, 121, (1927) · JFM 53.0170.04
[28] König, D., Theorie der endlichen and unendlichen Graphen, (1936) · Zbl 0013.22803
[29] Kwaśnik, M., Über einen {\it k}-antikern des gerichteten graphen, Zeszyty Naukowe, Wyższa Szkoła Iniynierżka w Zielonej Górze, Matematyka-Fizyka, 55, 33, (1980) · Zbl 0461.05055
[30] Marcu, Dănuţ, A method for finding the kernel of a digraph, An. Univ. Bucureşti Mat., 27, 41, (1978) · Zbl 0398.05039
[31] von Neumann, J., Zur theorie der gesellschaftsspiele, Math. Ann., 100, 295, (1928) · JFM 54.0543.02
[32] von Neumann, John; Morgenstern, Oskar, Theory of Games and Economic Behavior, (1944) · Zbl 0063.05930
[33] Neumann Lara, Víctor, Seminuclei of a digraph, An. Inst. Mat. Univ. Nac. Autónoma México, 11, 55, (1971) · Zbl 0286.05113
[34] Nigmatullin, R. G., The largest number of kernels in graphs with {\it n} vertices, Kazan. Gos. Univ. Učen. Zap., 130, 75, (1970)
[35] Richardson, M., On weakly ordered systems, Bull. Amer. Math. Soc., 52, 113, (1946) · Zbl 0060.06506
[36] Richardson, Moses, Solutions of irreflexive relations, Ann. of Math. (2), 58, (1953) · Zbl 0053.02902
[37] Richardson, Moses, Extension theorems for solutions of irreflexive relations, Proc. Nat. Acad. Sci. U.S.A., 39, 649, (1953) · Zbl 0053.02903
[38] Richardson, Moses, Relativization and extension of solutions of irreflexive relations, Pacific J. Math., 5, 551, (1955) · Zbl 0068.04203
[39] Romanowicz, Zbigniew, A remark on a theorem of Richardson, Prace Nauk. Inst. Mat. Fiz. Teoret. Politechn. Wrocław., 43, (1972) · Zbl 0253.05101
[40] Roth, AlvinE.; Karamardian, S.; Garcia, C. B., A fixed point approach to stability in cooperative games, Fixed points: algorithms and applications (Proc. First Internat. Conf., Clemson Univ., Clemson, S.C., 1974), 165, (1977), Academic Press, New York · Zbl 0418.90094
[41] Roth, AlvinE., A lattice fixed-point theorem with constraints, Bull. Amer. Math. Soc., 81, 136, (1975) · Zbl 0319.06005
[42] Roth, AlvinE., Subsolutions and the supercore of cooperative games, Math. Oper. Res., 1, 43, (1976) · Zbl 0457.90095
[43] Roth, AlvinE., Two-person games on graphs, J. Combin. Theory Ser. B, 24, 238, (1978) · Zbl 0391.05031 · doi:10.1016/0095-8956(78)90026-6
[44] Roth, AlvinE., A note concerning asymmetric games on graphs, Naval Res. Logist. Quart., 25, 365, (1978) · Zbl 0438.90119
[45] Rudeanu, S., Notes sur l’existence et l’unicité du noyau d’un graphe, Rev. Française Recherche Opérationelle, 8, 345, (1964) · Zbl 0129.40103
[46] Rudeanu, S., Notes sur l’existence et l’unicité du noyau d’un graphe II, Applications des équations booléennes, Rev. Française Recherche Opérationelle, 10, 301, (1966) · Zbl 0149.21403
[47] Relationen, graphen und strukturenInterner Bericht.Institut für Informatik der Techn. Univ. MünchenVorlesungsskriptum 1974/75
[48] Relations, graphs and programs(to appear)
[49] Smith, CedricA. B., Graphs and composite games, J. Combinatorial Theory, 1, 51, (1966) · Zbl 0141.36101
[50] Sprague, R., Über mathematische kampfspiele, Tohoku Math. J., 41, 438, (193536) · Zbl 0013.29004
[51] Sprague, R., Über zwei abarten von nim., Tohoku Math. J., 43, 351, (1937) · Zbl 0017.14602
[52] Steinhaus, H., Definitions for a theory of games and pursuit, Naval Res. Logist. Quart., 7, 105, (1960) · Zbl 0093.33002
[53] Ströhlein, T., Untersuchungen über kombinatorische Spiele, (1970)
[54] Ströhlein, T.; Nolemeier, H., Iterative berechnung der kerne eines graphen und der Lösung eines spiels, Graphen, Algorithmen, Datenstrukturen (Zweite Fachtagung über Graphentheoretische Konzepte der Informatik, Göttingen, 1976), (1976), Hanser, Munich · Zbl 0368.05042
[55] Ströhlein, T.; Zagler, L., Analyzing games by Boolean matrix iteration, Discrete Math., 19, 183, (1977) · Zbl 0364.90121
[56] Ergebnisse einer vollständigen analyse von schachendspielen-König und turm gegen König-König und turm gegen König and LäuferTUM-INFO-09-78-00-FBMAInstitut für Informatik der Techn. Univ. München1978
[57] Szamkołowicz, Lucjan, Sur la classification des graphes en vue des propriétés de leurs noyaux, Prace Nauk. Inst. Mat. Fiz. Teoret. Politechn. Wrocław. Ser. Studia i Materiały, 15, (1970) · Zbl 0264.05125
[58] Tarski, Alfred, A lattice-theoretical fixpoint theorem and its applications, Pacific J. Math., 5, 285, (1955) · Zbl 0064.26004
[59] Tinhofer, G., Über die bestimmung von kernen in endlichen graphen, Computing (Arch. Elektron. Rechnen), 9, 139, (1972) · Zbl 0263.05109
[60] Varvak, L. P., Generalization of a kernel of a graph, Ukrainian Math. J., 25, 78, (1973) · Zbl 0261.05127
[61] Vincke, Philippe, Hypergraphes orientés, Cahiers Centre Études Recherche Opér., 17, 407, (1975) · Zbl 0329.05109
[62] Vincke, Philippe, Quasi-kernels of minimum weakness in a graph, Discrete Math., 20, 187, (197778) · Zbl 0381.05048 · doi:10.1016/0012-365X(77)90057-7
[63] Wythoff, W. A., A modification of the game of nim, Nieuw Arch. Wisk., 7, 199, (190507) · JFM 37.0261.03
[64] Über eine anwendung der mengenlehre auf die theorie des schachspielsProc. 5th International Congress MathematicsVol. IICambridge1912501504
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.