Page 22 - 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. 22
1.2 Voltage graphs
Lifting walks: Suppose u v -walk W in G corresponds to sequence of edges/reverse edges
in G that is f 1 f 2 . . . f d . Say net voltage of W is α(W ) = α( f 1)α( f 2) . . . α( f d ). If start at a
vertex (u , g ) in G α and follow lifted walk W˜ in G α, will end at (v, g α(W )).
In particular, if W is a facial walk in G starting at u , will end at (u , g α(W )). Will
come back to original vertex (u , g ) if repeat r times where r is the order of α(W ) in
Γ. Thus, each face of degree d in G becomes a face of degree d r in G α where r is the
order in Γ of the net voltage of the facial walk. Face length does not change exactly
when net voltage is the identity (face satisfies Kirchoff Voltage Law, KVL).
Orientability: If original embedding of G is orientable, derived embedding will be ori-
entable. If original embedding is nonorientable derived embedding could end up
being orientable if all 1-sided walks lift to 2-sided walks.
Gross and Tucker [GT, 4.1.6] have algorithm based on reducing voltages in a span-
ning tree to the identity; won’t discuss details.
But if voltage group has odd order all 1-sided closed walks have net voltage of
odd order, must be repeated an odd number of times to close up in derived
embedding, stay 1-sided, so embedding stays nonorientable.
More general voltage graphs
Permutation/group action voltage graphs: Gross and Tucker describe ‘permutation
voltage graphs’ using permutation groups. Permutation groups are equivalent to
group actions so can also describe that way. Suppose have right action of group Γ
on set S: for each s ∈ S, g ∈ Γ can form s g obeying natural rules.
Then given graph G with edges oriented and voltage α(e +) ∈ Γ for each edge e , can form
derived graph with
V (G α) = V (G ) × S.
For each e + from u to v in G with α(e +) = a , add an edge (e +, s ) in G α from (u , s )
to (v, s a ) for every s ∈ Γ. (Reverse of (e +, s ) is (e −, s a ).)
Can lift embedding of G to derived embedding of G α in same way as for ordinary
voltage graphs: lift vertex rotations and edge twists.
Final remark: Voltage graphs are straightforward to understand but may not be most
convenient representation for particular applications. For very symmetric graphs a
voltage graph representation of an embedding may have only one or two vertices
and many edges, making it hard to keep track of where the edges go. So will look at
alternative, current graphs, and then later another alternative, transition graphs.
Lifting walks: Suppose u v -walk W in G corresponds to sequence of edges/reverse edges
in G that is f 1 f 2 . . . f d . Say net voltage of W is α(W ) = α( f 1)α( f 2) . . . α( f d ). If start at a
vertex (u , g ) in G α and follow lifted walk W˜ in G α, will end at (v, g α(W )).
In particular, if W is a facial walk in G starting at u , will end at (u , g α(W )). Will
come back to original vertex (u , g ) if repeat r times where r is the order of α(W ) in
Γ. Thus, each face of degree d in G becomes a face of degree d r in G α where r is the
order in Γ of the net voltage of the facial walk. Face length does not change exactly
when net voltage is the identity (face satisfies Kirchoff Voltage Law, KVL).
Orientability: If original embedding of G is orientable, derived embedding will be ori-
entable. If original embedding is nonorientable derived embedding could end up
being orientable if all 1-sided walks lift to 2-sided walks.
Gross and Tucker [GT, 4.1.6] have algorithm based on reducing voltages in a span-
ning tree to the identity; won’t discuss details.
But if voltage group has odd order all 1-sided closed walks have net voltage of
odd order, must be repeated an odd number of times to close up in derived
embedding, stay 1-sided, so embedding stays nonorientable.
More general voltage graphs
Permutation/group action voltage graphs: Gross and Tucker describe ‘permutation
voltage graphs’ using permutation groups. Permutation groups are equivalent to
group actions so can also describe that way. Suppose have right action of group Γ
on set S: for each s ∈ S, g ∈ Γ can form s g obeying natural rules.
Then given graph G with edges oriented and voltage α(e +) ∈ Γ for each edge e , can form
derived graph with
V (G α) = V (G ) × S.
For each e + from u to v in G with α(e +) = a , add an edge (e +, s ) in G α from (u , s )
to (v, s a ) for every s ∈ Γ. (Reverse of (e +, s ) is (e −, s a ).)
Can lift embedding of G to derived embedding of G α in same way as for ordinary
voltage graphs: lift vertex rotations and edge twists.
Final remark: Voltage graphs are straightforward to understand but may not be most
convenient representation for particular applications. For very symmetric graphs a
voltage graph representation of an embedding may have only one or two vertices
and many edges, making it hard to keep track of where the edges go. So will look at
alternative, current graphs, and then later another alternative, transition graphs.
