Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Nim-Regularity of Graphs. | Nim-Regularity of Graphs Nathan Reading School of Mathematics University of Minnesota Minneapolis MN 55455 reading@ Submitted November 24 1998 Accepted January 22 1999 Abstract. Ehrenborg and Steingrimsson 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. Mathematics Subject Classification 90D05 90D43 90D44 90D46. 1. Introduction In 1 Ehrenborg and Steingrimsson defined simplicial Nim a variant on the classic game of Nim. In simplicial Nim two players take markers from a number of piles. The piles are considered to be the vertices of some simplicial complex and a legal move consists of choosing a face of the complex and removing markers from any or all piles in the face. The number of markers removed from each pile in the chosen face is arbitrary and independent of the number removed from any other pile except that at least one marker must be removed. The winner is the player who removes the last marker. For some simplicial complexes called Nim-regular complexes the winning strategy can be described using a Nim-basis and the strategy is similar to the winning strategy of standard Nim. Standard Nim can be described as simplicial Nim on a complex whose faces are all single vertices and such a complex is Nim-regular . They 1 also raise the following question Question . Does a Nim-basis if it exists necessarily consist of the disjoint unions of circuits of the complex The author wishes to thank Vic Reiner for many helpful conversations. 1 2 THE ELECTRONIC JOURNAL OF COMBINATORICS 6 1999 R11 Here a circuit is a .
