Page 39 - 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. 39
k Ellingham: Construction Techniques for Graph Embeddings 27
hamilton cycle embedding of Kn,n,n . Every face has an a b c -pattern (useful for tripling
construction mentioned in section on surgery). If n ≥ 3 is not twice a prime then such a
latin square exists.
For n odd can again use Zn , addition table of n . Much trickier for even n .
1.8 Bouchet’s covering triangulations
Idea: Lift triangulation of G to triangulation of G [Km ] = G(m), graph where we replace
each x ∈ V (G ) by m independent vertices (x , i ), i ∈ m , and (x , i )(y , j ) ∈ E (G(m) ⇔
x y ∈ E (G ), i.e. each edge is replaced by a copy of Km,m . Original paper is [Bo78b].
Definition: Suppose G is eulerian (every vertex has even degree) and Ψ is a triangulation
of G . Let T = T (Ψ) be the set of triangles of Ψ. An m -valuation is a map φ : T → m .
An m -valuation is generative if the alternating sum around every vertex is a generator
of m .
Formalization: Make a bit more precise: a corner of the embedding is represented by a
(vertex, triangle) pair (x , t ). Assign a sign (x , t ) ∈ {−1, 1} to each corner so that the
signs alternate around every vertex. Define
φ(x ) = x∈t (x , t )φ(t )
for each vertex x . Then we want every φ(x ) to be a generator of m .
hamilton cycle embedding of Kn,n,n . Every face has an a b c -pattern (useful for tripling
construction mentioned in section on surgery). If n ≥ 3 is not twice a prime then such a
latin square exists.
For n odd can again use Zn , addition table of n . Much trickier for even n .
1.8 Bouchet’s covering triangulations
Idea: Lift triangulation of G to triangulation of G [Km ] = G(m), graph where we replace
each x ∈ V (G ) by m independent vertices (x , i ), i ∈ m , and (x , i )(y , j ) ∈ E (G(m) ⇔
x y ∈ E (G ), i.e. each edge is replaced by a copy of Km,m . Original paper is [Bo78b].
Definition: Suppose G is eulerian (every vertex has even degree) and Ψ is a triangulation
of G . Let T = T (Ψ) be the set of triangles of Ψ. An m -valuation is a map φ : T → m .
An m -valuation is generative if the alternating sum around every vertex is a generator
of m .
Formalization: Make a bit more precise: a corner of the embedding is represented by a
(vertex, triangle) pair (x , t ). Assign a sign (x , t ) ∈ {−1, 1} to each corner so that the
signs alternate around every vertex. Define
φ(x ) = x∈t (x , t )φ(t )
for each vertex x . Then we want every φ(x ) to be a generator of m .
