zbMATH — the first resource for mathematics

Nim-regularity of graphs. (English) Zbl 0913.90287
Electron. J. Comb. 6, No. 1, Research paper R11, 8 p. (1999); printed version J. Comb. 6, 155-162 (1999).
Summary: Ehrenborg and Steingrímsson defined simplicial Nim, and defined Nim-regular complexes to be simplicial complexes for which simplicial Nim has a particular type of winning strategy. We completely characterize the Nim-regular graphs by the exclusion of two vertex induced subgraphs, the graph on three vertices with one edge and the graph on five vertices which is complete except for one missing edge. We show that all Nim-regular graphs have as their basis the set of disjoint unions of circuits (minimal non-faces) of the graph.
91A43 Games involving graphs
91A05 2-person games
91A44 Games involving topology, set theory, or logic
91A46 Combinatorial games
Full Text: EMIS EuDML