Page 27 - 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. 27
k Ellingham: Construction Techniques for Graph Embeddings 15
In his book Ringel uses this current graph to construct a triangular embedding
of K14 − K2, the graph obtained by deleting one edge from K14. How does this work?
[Hints: keep only one component; add vertices in large faces.]
Exercise: Suppose we have a voltage graph G using group Γ, and we take a vertex v and a
constant g ∈ Γ. If we right multiply all voltages on edges into v by g , and left multiply
all voltages on edges out of v by g −1, then the derived graph stays unchanged, except
that vertex (v, h) is now labelled vertex (v, h g ) for each h ∈ Γ.
Prove that if we have a gem with assigned voltages, such that the net voltage
around every red-blue cycle is the identity, then we can modify the voltages as in
the previous paragraph, so that all red and blue edges have identity voltage. [Then
all nontrivial voltages are on yellow edges; this is the main step in proving that assign-
ing voltages to gems is effectively the same as Archdeacon’s assignment of voltages
to the medial graph.]
1.4 Bouchet’s diamond sum
Definition: To take the diamond sum of two graphs G and G we take vertices v in G and
v in G , so that degG (v ) = degG (v ), delete the two vertices, and identify their neigh-
bours together. We denote this as G G (where v , v , and the particular identification
of their neighbours are understood to be known).
We can extend this to two embeddings Ψ of G and Ψ of G : when we delete v and v we
cut along a curve through their neighbours, and we glue the surfaces together (to get
connected sum surface Σ#Σ ). The neighbours must be identified in rotation order.
We denote this as Ψ Ψ .
Note that if Ψ, Ψ have Euler genus , respectively, then Ψ Ψ has Euler genus + .
So if both embeddings are orientable, or both are nonorientable, we can just add the
genera of the surfaces.
Σ Σ′
|
delete, identify, glue
↓
Σ#Σ′
In his book Ringel uses this current graph to construct a triangular embedding
of K14 − K2, the graph obtained by deleting one edge from K14. How does this work?
[Hints: keep only one component; add vertices in large faces.]
Exercise: Suppose we have a voltage graph G using group Γ, and we take a vertex v and a
constant g ∈ Γ. If we right multiply all voltages on edges into v by g , and left multiply
all voltages on edges out of v by g −1, then the derived graph stays unchanged, except
that vertex (v, h) is now labelled vertex (v, h g ) for each h ∈ Γ.
Prove that if we have a gem with assigned voltages, such that the net voltage
around every red-blue cycle is the identity, then we can modify the voltages as in
the previous paragraph, so that all red and blue edges have identity voltage. [Then
all nontrivial voltages are on yellow edges; this is the main step in proving that assign-
ing voltages to gems is effectively the same as Archdeacon’s assignment of voltages
to the medial graph.]
1.4 Bouchet’s diamond sum
Definition: To take the diamond sum of two graphs G and G we take vertices v in G and
v in G , so that degG (v ) = degG (v ), delete the two vertices, and identify their neigh-
bours together. We denote this as G G (where v , v , and the particular identification
of their neighbours are understood to be known).
We can extend this to two embeddings Ψ of G and Ψ of G : when we delete v and v we
cut along a curve through their neighbours, and we glue the surfaces together (to get
connected sum surface Σ#Σ ). The neighbours must be identified in rotation order.
We denote this as Ψ Ψ .
Note that if Ψ, Ψ have Euler genus , respectively, then Ψ Ψ has Euler genus + .
So if both embeddings are orientable, or both are nonorientable, we can just add the
genera of the surfaces.
Σ Σ′
|
delete, identify, glue
↓
Σ#Σ′
