, ) = 2 by mex
, ) = 2 by mex
, by Lemma, vol.19
, by Lemma, vol.20
, by Lemma, vol.19
, by Lemma, vol.19
, Analysis of S 3,3,3 . The Grundy values are obtained using the mex rule and Lemmas 19 and 20. ? If k ? 0 mod 3, then G(S 1,2,2,k ) is computed as mex, ) = 0, and we are done
, ? If k ? 1 mod 3, then G(S 1,2,2,k ) is computed as mex, ) = 1, and we are done, 2000.
, ? If k ? 2 mod 3, then G(S 1) = 2, and we are done
, For all k ? 0, we have G(S 1,1,1,1,k ) = |S 1,1,1,1,k | + 1 mod 3, Lemma, vol.28
, For k = 1, 1 move is available from S 1,1,1,1,1 , leading to S 1,1,1,1 , and we conclude again thanks to Lemma 20 For k = 2, 3 moves are available from,1,1 , and S 1,1,1,2 , and we conclude thanks to Lemma 20 (and thanks to the case k = 0 above). The case k = 3 is not harder: 3 moves lead to, 3 , and we can conclude thanks to Lemma 20 and thanks to the cases k ? 2 above
, ,k . We conclude by induction, and thanks to Lemma 22, since we have: ? If k ? 0 mod 3, then G(S 1,1,1,1,k ) is computed as mex, ) = 0, and we are done, 2001.
, ? If k ? 1 mod 3, then G(S 1,1,1,1,k ) is computed as mex, ) = 1, and we are done
, ? If k ? 2 mod 3, then G(S 1,1,1,1,k ) is computed as mex(1, 0, ) = 2, and we are done
, Note that Lemma 2 is not invoked in the two previous proofs This is due to the cases S 1,1,2,k and S 1,1,1,k , which appear in the general case k ? 4, but do not satisfy the properties G(G) = |G| mod 3 and G(G) = |G| + 1 mod 3, respectively
, then S + S is always a P-position, with S defined as S 1 Let b(S) be the number of nontrivial branches of S, that is to say b(S) = |{i | i > 0}| if n = 0 and b(S) = |{i | i > 0}| + 1 otherwise If b(S) = 0 then we are trivially done thanks to Lemma 19 since S = P 1 and S = P 4 If b(S) = 1, then we conclude again by Lemma 19 since S and S are both paths If b(S) ? 2, then several cases follow. If A plays in S so as to leave S + S 1,...,t,n+3?k , with k ? {1, 2, 4}, then B replies by taking 3 ? k vertices in S if k ? {1, 2}, so as to leave S + S 1, which is a P-position, and if k = 4 then B replies by taking 1 vertex in S, so as to leave S 1,...,t,n?1 + S 1,...,t,n?1 , which is a P-position. If A plays elsewhere in S , then B can always copy A's move on S. For instance, if A removes k ? 1 vertices in S , so as to leave S ? S 1?k,...,t,n+3 , then B removes k vertices in S so as to leave S 1?k,t,n+3 . When B replies by mimicking A's move on S, B manages to leave T + T to A, with |T | < |S|, and we thus can conclude by induction that this is a P-position. If A plays in S, then we have to be careful. If A's move does not involve taking the center of S, then we are done, since B is again always able to copy A's move in S, this case, B can not always simply copy A's move in S , and we have to carry a more detailed analysis. For instance, if S = 1
, then B can not mimic A's move in S since it would disconnect S 1,1,1,2,3 , so as to leave P 2 + P 2 + P 3 A's move copied in S is not always a legal move Let us assume now that A's move in S can not be copied by player B in S . In this case, A was able to remove the centre of S, and this implies that S has at most 4 nontrivial branches, and that S has at most one more nontrivial branch than S. Note also that A removed strictly more than 1 vertex to S, and exactly b(S) ? 1 branches of S (if A empties S then B can trivially copy A's move on S so as to leave P 3 ) Three cases and several subcases follow. We will denote by k the number of vertices removed by A. Case (i): b(S) = 2. Without loss of generality let us assume S = S 1,2 with 1 ? 1 ? 2 . As in the case of Theorem 16, if there is a long enough branch in S (w.r.t the number of vertices removed by A), then we will proceed by a mirror argument, since S is actually a path P 1+2+1 . More precisely, if k ? 2 , then we may consider A actually played so as to leave S 1,2?k + S , and in this case player B can copy A's move on S , and we are done, Let us assume now that k > 2 . If k = 2, then S = S 1,1 , and we may have either S = S 1, 2003.
, If k = 4, then there are several subcases
, then A leaves ? + S = S and we may have either S = P 7 or S = S 1,2,3 . If S = P 7 , then A may remove 1 vertex from P 7 so as to leave P 6 , which is a P-position. If S = S 1,2,3 , then A may remove 1 vertex from S 1
, then A leaves P 1 + S and we may have either S = P 8 or S = S 1,3,3 . If S = P 8 , then A may remove 1 vertex from P 8 so as to leave P 1 + P 7 , which is a P-position. If S = S 1,3,3 , then A may remove 1 vertex from S 1
, then A leaves P 1 + S and we may have either S = P 8 or S = S 2,2,3 . If S = P 8 , then A may remove 1 vertex from P 8 so as to leave P 1 + P 7 , which is a P-position. If S = S 2,2,3 , then A may remove 1 vertex from S 2
, then A leaves P 2 + S and we may have either S = P 9 or S = S 2,3,3 . If S = P 9 , then A may remove 1 vertex from P 9 so as to leave P 2 + P 8 , which is a P-position. If S = S 2,3,3 , then A may remove 1 vertex from S 2
, then A leaves P 3 + S and we may have either S = P 10 or S = S 3,3,3 . If S = P 10 , then A may remove 1 vertex from P 10 so as to leave P 3 + P 9 , which is a P-position. If S = S 3,3,3 , then A may remove 1 vertex from S 3
, Let us denote S = S 1 In this case, we must have k = 4. Two subcases follow. ? If S = S 1,1,3 , then A leaves P 3?1 + S , and we may have S =, Case (ii): b(S) = 3
, If 3 ? 0 mod 3, B may reply by taking 1 vertex in S , so as to leave P 3?1 + S 13 is a P-position. If 3 ? 1 mod 3, B may reply by taking 2 vertices in S , so as to leave P 3?1 + S 1,1,1,3 . Indeed, from Lemma 22, Indeed, from Lemma 24, we know that G(S 1,1,2,3 ) = 2 = G(P 3?1 ), thus P 3?1 + S 1 If 3 ? 2 mod 3, B may reply by taking 1 vertex in S , so as to leave P 3?1 + S 1,1 ) = 1 = G(P 3?1 ), thus P 3?1 + S 1,1, p.3
, 3+3 , then B removes 4 vertices from S , so aas to leave P 3?1 + P 3?1
, then B removes 4 vertices from S , so aas to leave P 3?1 + P 3+2
, B can reply by taking 1 vertex in S , so as to leave P 3 + S 13+3 , then B may reply by removing 1 vertex from S , so as to leave P 3 + P 3+3 , which is a P-position. If S = S 1,5,3 , then B may reply by removing 1 vertex from S , so as to leave P 3 + P 3+6, or S = S 2,4,3 . If S = S 1 ) = G(P 3 ) = 3 mod 3. If S = S 1
, then a good answer for B is then to remove 2 vertices from S , so as to leave P 4 + S 1,1,1,1,4 , which is a P-position, since we know from Lemma, Case (iii): b(S) = 4, pp.4-4
, which is a P-position. If S = S 1,1,4,4 , then B may remove 4 vertices from S , so as to leave P 4 + S 1,1,4 , which is a P-position, since we know from Lemma, pp.4-4
, Our main results deal with graphs to which we append paths, for which we were able to derive a very general result showing that there is always ultimate periodicity, in the sense that, for any finite set L, there exists two integers k 0 and T such that G L (G u P k+T ) = G L (G u P k ), whenever k ? k 0 (Theorem 1) Is it true that the period T is the same as the period of the game played on paths? We then managed to prove pure periodicity results in some particular cases. We showed that, for some classes of graphs and sets L, k ) holds starting from n 0 = 0. This is the case, for instance, for simple stars when playing CSG({1, . . . , N }) (Proposition 8), for subdivided stars when playing CSG({1, 2, 3}) or CSG({1, p.4
, even in graphs as structurally simple as subdivided stars, pure periodicity is not the general setting, even if the game is purely periodic when played in paths. We proved, for instance, Theorem 10 that we only have ultimate periodicity in subdivided stars of type S 1,k,l for the game CSG({1, . . . , N })
, Combinatorial Analysis of a Subtraction Game on Graphs, Retrieved from arXiv, pp.1507-05673, 2015.
, Lessons in play: an introduction to combinatorial game theory, 2007.
, Octal Games on Graphs: The game 0.33 on subdivided stars and bistars, Theoret. Comput. Sci
URL : https://hal.archives-ouvertes.fr/hal-01418153
, Winning ways for your mathematical plays, 2001.
, Kayles on the way to the stars, International Conference on Computers and Games, 2004.
, A Nim game played on graphs, Theoretical Computer Science, vol.304, issue.1-3, pp.387-399, 2003.
DOI : 10.1016/S0304-3975(03)00292-5
, A Nim game played on graphs II, Theoretical Computer Science, vol.304, issue.1-3, pp.401-419, 2003.
DOI : 10.1016/S0304-3975(03)00293-7
URL : https://doi.org/10.1016/s0304-3975(03)00293-7
, Unsolved problems in Combinatorial Games, Games of No Chance 29, 1996.
DOI : 10.1090/psapm/043/1095545
URL : http://www.msri.org/publications/books/Book29/files/unsolved.pdf
, Polynomial Time Graph Families for Arc-Kayles, Integers, p.16, 2016.
, On the complexity of some two-person perfect-information games, Journal of Computer and System Sciences, vol.16, issue.2, pp.185-225, 1978.
DOI : 10.1016/0022-0000(78)90045-4
, Combinatorial game theory, 2013.
DOI : 10.1090/gsm/146
, Tohoku Mathematical Journal, First Series, vol.41, pp.438-444, 1935.