polyomino graphs

Thane Plambeck tplambeck at gmail.com
Wed Feb 7 18:54:35 CET 2007

Hi seq-fanners,

I'm interested in the number G(n) of non-isomorphic undirected graphs
obtained in the following way:

Start with the set of polyominos of order n.  For each one, put a
vertex in the middle of each of its cells.  Then draw all edges
between pairs of vertices that share an edge of the polyomino.

These graphs arise naturally in the analysis of end-games of various
combinatorial games.  For example, they arise in the game of Cram (see
Winning Ways, chapter 15, "Chips and Strips").

Anyway, by hand I've computed (starting at n=1)

1,1,1,3,4,10,17, ...

and have not found this sequence in the OEIS.

It sure would be nice to have someone confirm and/or extend these
numbers ... any takers?

Thane Plambeck
tplambeck at gmail.com

More information about the SeqFan mailing list