The Graph type of a Polyomino

This is a continuation of the post radlams.

A graph is some dots (called nodes or vertices) and lines between some of them (called edges). It’s not the geometry of the graph that matters, just how the vertices are connected up by edges.

Associated to each polyomino is a graph, called the graph-type of the polyomino. You get it by putting a vertex at the center of each square and then adding edges between the vertices of adjacent squares:

It turns out (my friend Sean, a graph theorist, pointed this out to me) that whether or not a polyomino is a radlam depends only on its graph type.

Radlams can be pretty easily classified by their graph type. Basically they come in two infinite families. The open ones:

\qquad\qquad\vdots

And the closed ones:

\qquad\qquad\vdots

If you notice, there are no radlams of size p for p=4n+2 except for p=6, in which case we have the single radlam:

Making it unique.

In a subsequent post I will outline a proof of this classification theorem. (by the way, I’m pretty sure that I got all of them in the above lists. If not please let me know).

Advertisements
This entry was posted in polyominoes and tagged , , , . Bookmark the permalink.

2 Responses to The Graph type of a Polyomino

  1. Chris says:

    Ah, radlams. I had almost forgotten. Maybe we can get you in for a guest lecture this summer. When will you be available?

  2. Pingback: Proof of radlam Classification « Synchronicity

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s