Game on simple finite graphs

Consider the following game on graphs (no multiple edges, but graphs can be disconnected).

Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such that the number is the smallest non-negative integer that is not already assigned to its neighbours.

The game ends when all vertices have numbers assigned to them. The last player to make a move wins if and only if that vertex was assigned an odd number.

Even for path graphs (that is, $n$ vertices in a line, connected with edges), I have no idea for which $n$ the first player has a winning strategy.

Some computations suggests that the first player lose if $n=1, 2, 4, 5, 6, 7, 9, 11, 13, 15$. I don't find a hit in OEIS that seem to make sense.

• Same for other values of $n$. I suspect you meant "smallest positive integer" instead of non-negative. – Théophile Jun 17 '15 at 16:16
• Maybe this was your intention, but there is a canonical labelling scheme for graphs that uses this idea of picking the minimal (or maximal) label for the neighbours that has not already been chosen. It's by Plavšić, Vukičević, and Randić titled "On Canonical Numbering of Carbon Atoms in Fullerenes: C60 Buckminsterfullerene" – gilleain Jun 17 '15 at 16:24
• I think you still have the win/lose flipped. If you're using smallest positive integer, then on a single vertex, the first player wins (he is the last one to make a move, and assigns the odd number 1). Also, you should probably use the terminology "paths" rather than "line graphs", since a line graph is something completely different. – Perry Elliott-Iverson Jun 17 '15 at 18:00
• Ah, i think someone made an edit and changed non-negative to positive integers. Now it should be fine. – Per Alexandersson Jun 17 '15 at 18:31
• Note that which player will play last is determined by the parity of the number $n$ of vertices. Therefore the players are actually competing to determine the parity of the last vertex chosen, with the first player wanting it to be even or odd corresponding to whether $n$ is even or odd, and the second player wanting the opposite. – hardmath Jun 18 '15 at 2:30

This is only a partial answer, mainly to add some observations which haven't been recorded but which don't fit neatly in comments.

General lemma

A vertex $v$ with $m$ edges will be labelled with a value at most $m$.

Proof: suppose the contrary. Then $v$ is labelled with a value greater than $m$, so its adjacent vertices must include among their labels all values from $0$ to $m$, so there must be at least $m+1$ adjacent vertices. But $v$ only has $m$ edges.

Corollary

If a vertex $v$ has $m$ edges, we can attach to the graph a vertex $u$ with label $(m+1)$ and the edge $(u, v)$. This does not affect the game-theoretic value of the position.

Proof: we were never going to label $v$ with a value of $(m+1)$ or greater, so $u$ is irrelevant to the labelling of $v$. And since it has no edges to any other vertex, it is irrelevant to the labelling of every other vertex.

Corollary for path graphs

Instead of adding additional vertices at the ends with label $-1$, as in hardmath's answer, we can add additional vertices at the ends with label $2$.

Note that this shows directly that path(A,-1,K) should have the same value as path(A,2,K), and there must be something wrong with his table. I get a table with a few disagreements:

(A,C)\K =  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |...even | odd |
=====================================================================
( 0, 0) :  W :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 1, 0) :  L :  W :  L :  W :  L :  W :  L :  W :  L :...  W  |  L  |
( 2, 0) :  W :  W :  W :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 1, 1) :  L :  W :  L :  W :  L :  W :  L :  W :  L :...  W  |  L  |
( 2, 1) :  L :  W :  L :  W :  L :  W :  L :  W :  L :...  W  |  L  |
( 2, 2) :  L :  L :  W :  L :  L :  L :  L :  W :  L :...  W  |  L  |


I do agree that it seems that for $n > 7$ all single-path positions are a win if there are an even number of unlabelled vertices, and a loss if there are an odd number. I suspect that it may be possible to prove this by induction with a sufficiently strong inductive hypothesis. A sketch of the inductive step:

• If $n$ is even and greater than 8, path(A,C,n) reduces in one step to path([A=0],C,n-1) (using Iverson notation), which is a losing (P) position. Therefore path(A,C,n) is a winning (N) position.
• If $n$ is odd and greater than 8, a play at one of the ends of the path reduces it to a winning position path([A=0],C,n-1) or path(A,[C=0],n-1). Therefore if we want to find a losing position for our opponent, we must split into two paths as path(A,0,i) + path(0,C,n-1-i) for some $1\le i\le n-2$. We now have a further case-split:

• $i$ is odd, and one or both of the paths is a special-case winning position for small odd $K$.
• $i$ is odd and we hand our opponent a sum of two losing odd paths.
• $i$ is even and we hand our opponent a sum of two winning even paths.

The first sub-case can probably be dealt with by brute force. The other two might be amenable to joint treatment if we show that the sum of a losing odd path and a winning even path is a losing position. (Empirically this seems to be the case. A possible approach would be to strengthen to "the sum of a losing odd position and a winning even position with a total of $n$ unlabelled vertices is a losing position; the sum of two losing odd positions or two winning even positions with a total of $n$ unlabelled vertices is a winning position" and try to induct on $n$).

• I don't see why the games on path(A,-1,K) and path(A,2,K) should be equivalent, nor why path(2,2,K) and path(-1,-1,K) give equivalent games for small K. Clearly the first player loses for path(-1,-1,1) and wins for path(2,2,1) in a single move. Perhaps you could highlight another discrepancy for K < 8? – hardmath Jul 13 '15 at 16:37
• @hardmath, with both path(A,-1,K) and path(A,2,k) the value which will be played into the gap next to B can only be 0 or 1, and in particular is never -1 or 2 in either case; in fact, we could go further and say that for any $B \not\in \{0,1\}$, path(A,-1,K) = path(A,B,K). path(2,2,1) has only one possible move, which is to play 0 into the gap and lose, exactly as with path(-1,-1,1). Other discrepancies are (1,0,3), (1,0,5), (1,0,7), (2,0,7), (1,1,2), (1,1,7), (2,1,1), (2,1,5), (2,1,7). – Peter Taylor Jul 13 '15 at 17:53
• We apparently interpret the game differently. If the "board" is (2,_,2), then the only move puts 3 into the gap and wins, whereas if the board is (-1,_,-1), then as you say the only move puts 0 in the gap and loses. – hardmath Jul 13 '15 at 17:57
• @hardmath, "the smallest non-negative integer that is not already assigned to its neighbours". Since the only integers assigned to the neighbours are 2 and 2, the smallest unassigned non-negative one is 0. – Peter Taylor Jul 13 '15 at 17:59
• I revised my programming and accordingly confirm the results you tabulated above. The game is somewhat simpler than what I considered. For example there are no "new" endpoints 2 created from breaking longer segments into shorter "subpaths". So the prospect of a proof by induction seems brighter now, as you outline. – hardmath Jul 17 '15 at 13:49

The cycle graphs and path graphs are easily related, as far as winning vs. losing positions. Upon making the initial move in a cycle $C_n$ graph, it becomes equivalent for the opposing player to moving in a path $P_{n+1}$ where the first and last nodes are already numbered $0$ (and the $n-1$ nodes between are still unnumbered).

Indeed it is subsequently more efficient to represent the intermediate graph game states as a "union" of path subgraphs whose unnumbered nodes are disjoint. It is convenient to consider artificially adding nodes numbered $-1$ to the ends of otherwise unnumbered path graphs, so that every unnumbered node has exactly two neighbors, and this does not affect the outcomes of games.

That is, an initial path graph $P_k$ is equivalent to a path graph $P_{k+2}$ with first and last nodes numbered $-1$. The next move would number one of the $k$ unnumbered nodes, effectively dividing the game's graph into two paths, each with a zero at one end and a $-1$ at the other, or leaving a single stretch $P_{k+1}$ with a zero at one end and a $-1$ at the other.

In this fashion any intermediate game state for a cycle $C_n$ or path $P_n$ can be represented as a sorted collection of "components" that partition the unnumbered nodes in arrangements compactly specified by $p(a,b,k)$, where $a \ge b$ are numbers of the two endpoints of a path that otherwise consists of $k \gt 0$ unnumbered nodes between those endpoints.

Update:

Using these more compact "path" segments to represent the "board" (partially numbered graphs), symmetries/equivalences can be more efficiently recognized. Runs with fifteen unnumbered nodes now take about several minutes rather than the better part of a day.

A striking pattern emerges. The table below shows the winning or losing status of a single path segment path(A,C,K), having K yet unnumbered nodes between endpoints numbered A and C respectively:

(A,C)\K =  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |...even | odd |
=====================================================================
(-1,-1) :  L :  L :  W :  L :  L :  L :  L :  W :  L :...  W  |  L  |
( 0,-1) :  W :  W :  W :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 0, 0) :  W :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 1,-1) :  L :  W :  L :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 1, 0) :  L :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 1, 1) :  L :  L :  L :  W :  L :  W :  W :  W :  L :...  W  |  L  |
( 2,-1) :  W :  W :  W :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 2, 0) :  W :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 2, 1) :  W :  W :  L :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 2, 2) :  W :  W :  W :  L :  W :  W :  W :  W :  L :...  W  |  L  |


While columns for $k=1,\ldots,7$ contain a good bit of variation, longer paths seem to be exclusively winning for $k$ even and losing for $k$ odd, regardless of the endpoints. Computations have been done for all the endpoints shown up to $k=15$, and for "default" endpoints $a=c=-1$ with $k=16,17$ as well.

Some general results

Intuitively there should be some Nim-like rule for determining the winning or losing status of such collections of paths with numbered endpoints. So far I have only been able to prove the following easy lemma.

Suppose the game state $S$ can be expressed as the union of two subgraphs $S_1$ and $S_2$ such that no unnumbered node is shared by $S_1$ and $S_2$. If $S_1$ and $S_2$ are losing positions (i.e. for the player required to move next), and if both $S_1$ and $S_2$ have even counts of unnumbered nodes, then $S$ is a losing position (and also has an even count of unnumbered nodes, aka moves left).

The proof is easy. As the current player moves in $S_1$ or $S_2$, the opponent can responds with a perfect defending move accordingly. The updated game state is again a union of two losing positions with even numbers of moves left in each, unless such a pair of moves "finishes" $S_1$ or $S_2$, leaving only one unfinished subgraph with its losing position.

An immediate corollary to this is that if $S_1$ is a winning position with an odd number of moves left, and $S_2$ (disjoint from $S_1$ as to unnumbered nodes) is a losing position with an even number of moves left, then the "union" of $S_1$ and $S_2$ is a winning position. The proof is just to observe that after making a winning move in $S_1$, one is left with a losing position (either by the preceding lemma, or by exhausting $S_1$ leaving only $S_2$).

• The $p(a,b,k)$ notation can be improved slightly by observing that the actual values of $a$ and $b$ don't matter: all that matters is $a - b$ and $b\mod 2$. – Peter Taylor Jun 30 '15 at 15:21
• @PeterTaylor: That's an interesting idea. I tried to come up with something like that but could not convince myself. I'm doing some runs to tabulate the win/lose state for these segments. – hardmath Jun 30 '15 at 15:28
• Ah, hang on. That's not true for large values of $k$, because then a $0$ can be inserted in the middle of the path and the value of $b$ matters. I apologise for sending you down a blind alley. – Peter Taylor Jun 30 '15 at 16:06
• @PeterTaylor: While it is not enough just to know the parity of $b$ and $a-b$, we can still profit from classifying "equivalent" segments. Segments with $k=1$ are of two kinds, and segments with $k=2$ are of three kinds (accordingly as the next move in that segment will produce only one or either of the kinds of $k=1$ segment). Maybe there is an easy scheme only for fairly short paths, but it seems promising. – hardmath Jul 2 '15 at 13:00
• I added an answer which I believe explains the results for large path graphs (and sketches a proof). – joriki Aug 3 '15 at 14:20

The reason that, as others have noted, the player who wants the last number to be even wins on large path graphs is that the configuration $0..0$ (and also, less importantly, $1..1$) leads to an even number independent of the order of play, whereas the parity of the last number placed in the configuration $0..1$ depends on the order of play. Thus, when the "even" player sets up $0..0$, the other player has to spend two moves filling in the two dots to prevent these from being the last numbers, whereas there is no corresponding manoeuvre for the "odd" player.

A sketch for a proof that the even player wins sufficiently large path graphs: If the odd player goes first, she has to place a $0$. The even player creates a $0..0$ configuration. If the odd player plays elsewhere, the even player just continues improving his situation by creating more $0..0$ configurations. Likewise, if the odd player plays inside the $0..0$ to destroy it, the even player creates further such configurations (using the sufficiently available space). The best the odd player can do is to create one $0.0$ configuration per move, but for every move she spends doing that, the even player creates another $0..0$.

If the even player goes first, he plays somewhere in the middle. The odd player can then create one $0.0$, or can place a $1$ next to the $0$ in an attempt to destroy opportunities of $0..0$ creation. But the even player still has the other side to create a $0..0$. Then the odd player can create another $0.0$, or shield the $0$ on the other side with a $1$. But neither helps. If the odd player opts for $0.0$s, the even player can win either by creating more $0..0$s or by filling in the $0.0$s (since he's now half a move ahead in the filling race), and if the odd player opts for shielding $1$s, the even player can play another $0$ in a sufficiently distant part of the field and create another $0..0$ there.

Obviously there are some details to fill in to turn this into a rigorous proof, but it seems clear to me that this asymmetry, the ability to build a winning configuration that takes two moves to destroy whereas the other player can only build single winning spots, is the basic reason for the results for large path graphs.

• I've been trying to frame an argument about the last player's strategy to create/preserve winning moves (odd parity) as the game closes and the next-to-last player's counterstrategy (to remove winning moves/create losing (even parity) opportunities) overwhelming the former, at least on sufficiently long simple paths. – hardmath Aug 3 '15 at 16:31