Page 37 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 37
k Ellingham: Construction Techniques for Graph Embeddings 25
This construction is important: by varying the way the K3,3,3 embeddings are glued on,
was first construction of large number (c n2 ) of nonisomorphic triangular embed-
dings of given complete graphs Kn [BGGS00].
‘Doubling’ and ‘tripling’ for hamilton cycle embeddings of complete graphs: Due to
Ellingham and Stephens [ES09]/Ellingham and Schroeder [ES14b] Use hamilton cy-
cle embedding of regular complete bipartite/tripartite graph (known) to glue together
hamilton cycle embeddings of Kn to get hamilton cycle embedding of K2n−2 or K3n−3.
a0 b0 c0
For ‘tripling’, glue together: a1 b1 c1
(a) three hamilton cycle embeddings of Kn , each
with one vertex deleted, and
(b) one hamilton cycle embedding of
Kn−1,n−1,n−1 with at least one a b c -pattern
face (which we remove).
Result is hamilton cycle embedding of K3n−3. Rotation
around b1 shown to see how it works.
Exercise: Use adding a crosscap around a vertex to transform the embedding of K4,4 on
the torus, given in Section 4 above, into an embedding of K4,5 on N3.
1.7 Connections with design theory
Designs can often be used to help construct embeddings. Often need some kind of extra
condition to make sure we get proper rotations.
Biembeddings of Steiner triple systems
If we have a 2-face-colourable triangular embedding of Kn , then each colour class forms
a partition of the edges of Kn into triangles. In other words, we have a set of triples
chosen from n elements so that every pair occurs in exactly one triple: a Steiner triple
system (STS). Altogether this is a biembedding of Steiner triple systems.
Example: 2-face-colourable embedding of K7 on torus, shown below, is a biembedding
of the Fano plane (the unique up to isomorphism STS of order 7) with itself.
This construction is important: by varying the way the K3,3,3 embeddings are glued on,
was first construction of large number (c n2 ) of nonisomorphic triangular embed-
dings of given complete graphs Kn [BGGS00].
‘Doubling’ and ‘tripling’ for hamilton cycle embeddings of complete graphs: Due to
Ellingham and Stephens [ES09]/Ellingham and Schroeder [ES14b] Use hamilton cy-
cle embedding of regular complete bipartite/tripartite graph (known) to glue together
hamilton cycle embeddings of Kn to get hamilton cycle embedding of K2n−2 or K3n−3.
a0 b0 c0
For ‘tripling’, glue together: a1 b1 c1
(a) three hamilton cycle embeddings of Kn , each
with one vertex deleted, and
(b) one hamilton cycle embedding of
Kn−1,n−1,n−1 with at least one a b c -pattern
face (which we remove).
Result is hamilton cycle embedding of K3n−3. Rotation
around b1 shown to see how it works.
Exercise: Use adding a crosscap around a vertex to transform the embedding of K4,4 on
the torus, given in Section 4 above, into an embedding of K4,5 on N3.
1.7 Connections with design theory
Designs can often be used to help construct embeddings. Often need some kind of extra
condition to make sure we get proper rotations.
Biembeddings of Steiner triple systems
If we have a 2-face-colourable triangular embedding of Kn , then each colour class forms
a partition of the edges of Kn into triangles. In other words, we have a set of triples
chosen from n elements so that every pair occurs in exactly one triple: a Steiner triple
system (STS). Altogether this is a biembedding of Steiner triple systems.
Example: 2-face-colourable embedding of K7 on torus, shown below, is a biembedding
of the Fano plane (the unique up to isomorphism STS of order 7) with itself.
