Prisms

Scenario 1

In Scenario One we try and find the minimum amount of tile types while allowing the possibility that smaller complexes (fewer vertices and/or edges than the target graph) may be created from the set of tiles that needs to build the target graph. Right away, we realize that prism graphs of any size will require a minimum of two tile types since it would be impossible to match hatted and unhatted cohesive ends in any three-regular graph (all vertices of degree three) with just one tile type. We then create an algorithm for how to find a solution:

1) Draw prism with n number of sides

2) Add augmenting edges to create an Eulerian Cycle (even degree vertices).

3) Find an Eulerian circuit through prism, and add directed edges that follow the direction of the circuit.

4) Erase augmenting edges

5) Use the direction of each edge to label the vertices. Each edge directed into a vertex becomes a and each edge directed away from a vertex becomes â

After doing this, we find that all vertices have either one ingoing edge and two outgoing edges or two ingoing edges and one outgoing edge, corresponding to the tile types aaâand aââ. This holds true for prisms of any size, so we can conclude that the minimum number of tiles for prisms under Scenario One is two.

Scenario 2

We found that no prisms could be made with just one tile type and one bond-edge because of the fact that all vertices are of degree three, which would make it impossible to match hatted and unhatted bond-edges. Likewise, using two tile types with one bond-edge type while not being able to make any smaller complete complex is impossible because the only tile options are a³, â ³, aâ², and a²â, which only yields smallest complete complexes of two or four vertices (triangular prisms have six vertices). Also, two tile types with two or more bond-edge types aren’t possible because of the theorem that states: if G is a graph with n>2 vertices, then B₂(G)+1 ≤ T₂(G).

With these things in mind, we were able to find pots of three tile types and two bond-edges to fit the criteria of Scenario 2 for triangular, rectangular, and pentagonal prisms. We used the reduced row echelon form to confirm that the given pot used to the target graphs could not make any smaller complete complexes. The figures below show the pots and tiled figure for triangular, rectangular, pentagonal, hexagonal, heptagonal, octagonal, and nonagonal prisms.