[math-fun] # of non-isomorphic polyomino graphs
I'm not finding the following sequence in the OEIS, probably because I'm blind to a mistake I've made in counting them. Consider the set of graphs G(n) constructed in the following way. Take the set of polyominos with n cells. For each polyomino P in turn, put a vertex at the center of each cell, and draw edges between two vertices if they share an edge in the polyomino, obtaining a plain old unidirected graph G with n vertices. I'm interested in the # of nonisomorphic graphs that are obtained in this way, for each n. Starting at n=1, I get the sequence 1,1,1,3,4,10 and hits in the OEIS that don't look like they fit for larger n -- Thane Plambeck tplambeck@gmail.com http://www.plambeck.org/ehome.htm
Aren't there 5 for n=5? --ms Thane Plambeck wrote:
I'm not finding the following sequence in the OEIS, probably because I'm blind to a mistake I've made in counting them.
Consider the set of graphs G(n) constructed in the following way. Take the set of polyominos with n cells. For each polyomino P in turn, put a vertex at the center of each cell, and draw edges between two vertices if they share an edge in the polyomino, obtaining a plain old unidirected graph G with n vertices.
I'm interested in the # of nonisomorphic graphs that are obtained in this way, for each n.
Starting at n=1, I get the sequence
1,1,1,3,4,10
and hits in the OEIS that don't look like they fit for larger n
On 2/6/07, Mike Speciner <speciner@ll.mit.edu> wrote:
Aren't there 5 for n=5?
I, L, N, W, V, U, and Z all are isomorphic graphs (5 vertices in a line, degrees 1,2,2,2,1) F, T, and Y are four in a line with a branch of the side, degrees 1,2,3,1,1 P has four in a block with one off the side, degrees 2,2,2,3,1 And then there's X, with degrees 4,1,1,1,1 I know the degrees of the vertices isn't enough to prove the graphs isomorphic in general but in this case I think it's true that all the pentominoes with the same list of degrees are indeed isomorphic. So I get 4 ... --Joshua Zucker
Never mind. You're right, there are only 4. --ms Mike Speciner wrote:
Aren't there 5 for n=5?
--ms
Thane Plambeck wrote:
I'm not finding the following sequence in the OEIS, probably because I'm blind to a mistake I've made in counting them.
Consider the set of graphs G(n) constructed in the following way. Take the set of polyominos with n cells. For each polyomino P in turn, put a vertex at the center of each cell, and draw edges between two vertices if they share an edge in the polyomino, obtaining a plain old unidirected graph G with n vertices.
I'm interested in the # of nonisomorphic graphs that are obtained in this way, for each n.
Starting at n=1, I get the sequence
1,1,1,3,4,10
and hits in the OEIS that don't look like they fit for larger n
participants (3)
-
Joshua Zucker -
Mike Speciner -
Thane Plambeck