Flexible Tiles

Flexible tiles are tiles whose arms can bend freely (for example, the arms are able to form loops). They were introduced in [JKS99] and further discussed in [Ell+,JMS06,Sta06].

Design Constraints

If pot P = {t₁ . . . t_n}, and each tile t_j has A_i,jcohesive ends of type a_i and Â_i,j cohesive ends of type â_i, then the observations below are immediate consequences of requiring complexes to be complete.

a. A graph G with n vertices may be constructed from the pot P if and only if there are non- negative integers r_j for j = 1. . .p (representing the number of times each tile of type t_j is used in the construction of G) with Σ_(j)r_j = n and such that Σ_(j) r_jA_i,j = Σ_(j) r_j Â_i,j for all i. That is, the number of hatted cohesive ends of each type used in the construction of G must equal the number of unhatted cohesive ends of the same type that appear in the construction.

b. The total number of hatted cohesive end types must equal the total number of unhatted cohesive end types in a complete complex. While trivial, this observation will be useful in parity arguments.

Scenarios: Given a graph, we wish to know the minimum number of tile and bond-edge types that must be designed to construct the complex. We consider this question under three different conditions:

Scenario 1. We allow the possibility that graphical complexes of smaller size (that is, complexes representing graphs with fewer vertices and/or edges) than the target graph could be created from the set of tiles that builds the target graph.

Scenario 2. We allow the possibility that graphical complexes with the same number of vertices as, but not isomorphic to, the target graph could be created from the set of tiles that builds the target graph, but require that no complexes with fewer vertices can be built from the set of tiles that builds the target graph.

Scenario 3. We require that no complexes with less than or equal to the number of vertices of the target graph can be built from the set of tiles that builds the target graph.

Let T_i(G) equal the minimum number of tile types needed to build graph G in Scenario i, and B_i(G) equal the minimum number of bond edge types needed to build graph G in Scenario i. In each of these scenarios, we provide general upper and lower bounds for these values and determine specific values for some important classes of graphs.

Theorem. Let G be a graph with n > 2 vertices, and suppose P is a pot that realizes G using B₂(G) bond types and T tiles, where P does not realize any graph with fewer vertices than G. Then T ≥ B₂(G) + 1.

Additional Useful Vocabulary

Vertex degree sequence: (of a graph G) is the sequence, in increasing order, of degrees of each of the vertices of G. This sequence has repeated values if G has multiple vertices of the same degree.

Valency sequence: [av(G)] - of G - the sequence of vertex degrees of G without repeats

Even valency sequence: [ev(G)] the sequence of even degrees that appear in G

Odd valency sequence: [ov(G)] the sequence of odd degrees in G