Connected Sprouts

DOI10.2307/2974978MaRDI QIDQ4340674zbMATH OpenOpenAlexFDO

Authors Tao Kai Lam

Publication date 10 June 1997

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2974978

zbMATH Keywords

2-connectedgame of Sprouts

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Games involving graphs (91A43)

Review text

We correct an error in a paper by \textit{M. Copper} [Am. Math. Mon. 100, No. 5, 478-482 (1993; Zbl 0820.05018)] and answer some questions posed by him. Let \(G\) denote the graph obtained from a complete game of Sprouts on \(m\) vertices. If \(G\) is connected, we show that the lower bound on the number of moves is \(2m\) if \(1\leq m\leq 3\) and \(2m+1\) if \(m>3\). If \(G\) is 2-connected, the lower bound is \(\lceil \frac{7}{3}m-\frac{2}{3}\rceil\). The bounds are strict. An example of a simple cubic graph that cannot be obtained from a Sprouts game is also given.

Recommendations

• Graph Theory and the Game of Sprouts
• A modular approach to Sprouts
• Computer analysis of Sprouts with nimbers

Cited in

(3)

• A modular approach to Sprouts
• Algorithms for interactive Sprouts
• Planted Brussels Sprouts (after Ji-Propp)

This page was built for publication: Connected Sprouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4340674)