General Graph

Scenario 1 - Allow smaller complexes to be formed.

Theorem. You can create any graph using just one edge type (i.e. B₁ (G) = 1 for all G).

Theorem. av(G) ≤ T₁(G) ≤ ev(G) + 2ov(G), where av(G), ev(G), and ov(G) are the valency, even valency, and odd valency sequences respectively, and these bounds are tight.

Algorithm for creating the design:

Input: A target graph G.

Output: At most ev(G) + 2ov(G) tile types from which G may be constructed.

1. Create an augmented graph G' from G by adding edges between pairs of odd degree vertices. G' is then Eulerian.

2. Construct an Eulerian circuit for G', recording the orientation of each edge.

3. Delete the augmented edges, leaving an orientation of the original graph G.

4. Record a tile type with k cohesive ends of type a and l cohesive ends of type â whenever there is a vertex with in-degree and out-degree l.

Running Time: The running time will be O (|E|) since an Eulerian circuit can be found in linear time and the additional preprocessing and labeling work is also linear.

This implies that for k-regular graphs you will need either 1 or 2 types depending on whether k is even or odd.

Scenario 3 - Do not allow any smaller complexes or alternative complexes with the same size.

T₃ (G) ≥ X(G), where X(G) is the chromatic number of G.