For example, 4 squares can touch 3 others at at least one point, 12 squares can touch 3 others at exactly one point, and 14 squares can touch 3 others along part of an edge:

touching | touching at 1 point | touching along an edge |

Can you show that 25 squares can each touch 4 other squares? Can you show that 48 squares can each touch 4 other squares in exactly 1 point? Can you show that no finite collection of squares can each touch 4 squares along an edge? What are the corresponding minimum numbers for other shapes? Another way to look at this is: For a given planar regular graph, what is the smallest polyomino that can be arranged to have that adjacency graph? For definiteness, here we require the shapes to conform to the square grid and to touch along part of an edge. For example, there is a 8-omino that can realize the smallest 3-regular graph:

(found by Olexandr Ravsky) |

What are the smallest polyominoes (or other polyforms) that can realize the other small planar 3-regular and 4-regular graphs?

Have Regular Adjacency Graph

Shape | Touching 3 others | Touching 4 others | ||||
---|---|---|---|---|---|---|

any | 1 point | edge | any | 1 point | edge | |

4 | 12 | 14 (EP) | 25 (BG) | 48 (BG) | ∞ | |

4 | 8 | 8 | 15 | 26 | 24 | |

4 | 8 | 8 | 10 | 16 | 20 | |

4 | 8 | 8 | 15 (CP) | 22 | 32 | |

4 | 8 (GS) | 8 | 10 | 16 | 24 | |

4 | 8 | 6 (CP) | 10 (CP) | 18 | 16 | |

4 | 6 | 6 | 10 | 16 | 12 | |

4 | 6 (CP) | 6 | 14 | 14 | 16 | |

4 | ? | 4 (OR) | ? | ? | ? | |

4 | 4 | ∞ | 5 | 5 | ∞ | |

4 | 4 | 16 | 5 | 5 | ∞ | |

12 (CP) | 12 (CP) | 16 | ∞ | ∞ | ∞ | |

16 | 16 | ∞ | ∞ | ∞ | ∞ |

EP = Ed Pegg

BG = Branko Grünbaum

OR = Olexandr Ravsky

CP = Corey Plover

GS = George Sicherman

to Have Given 3-Regular Adjacency Graph

Graph | Min Size | Polyomino Arrangement | Min Size | Polyhex Arrangement |
---|---|---|---|---|

8 | (OR) | 4 | (GS) | |

4 | (CP) | 4 | (CP) | |

9 | ? | ? | ||

5 | 4 | |||

3 | 2 | |||

3 | 3 | |||

3 | 3 | |||

5 | 3 | |||

4 | 4 | |||

5 | 4 | |||

5 | 4 | |||

5 | 3 | |||

12 | ? | ? | ||

14 | ? | ? | ||

3 | (JD) | 2 |

OR = Olexandr Ravsky

GS = George Sicherman

CP = Corey Plover

JD = Joe DeVincentis

to Have Given 4-Regular Adjacency Graph

Graph | Min Size | Polyomino Arrangement | Min Size | Polyhex Arrangement |
---|---|---|---|---|

? | ? | ? | ? | |

6 | 6 | (GS) | ||

? | ? | ? | ? | |

14 | (JD) | 6 | ||

? | ? | ? | ? | |

? | ? | ? | ? | |

? | ? | ? | ? | |

? | ? | ? | ? | |

8 | (JD) | ? | ? |

GS = George Sicherman

JD = Joe DeVincentis

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 11/29/05.