Page 29 - 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. 29
k Ellingham: Construction Techniques for Graph Embeddings 17
Claim B: F (3, 6) and F (4, 4) hold.
Proof:
Claim S: F (m , 6) holds for all m .
Proof: By repeated diamond sums with K3,6 we can build up K3,6 → K 4, 6 → K 5, 6 → . . .,
and since f 0(3, 6) = 1 is integral the result follows from Claim D.
Claim B+: F (m , n ) holds if m , n ≤ 6.
Proof: Use Claim S if m = 6 or n = 6. Claim B covers F (4, 4), and also F (3, 6) from which
we also get F (3, 3), F (3, 4) and F (3, 6). We get F (4, 5) from F (4, 6), and F (5, 5) from F (5, 6).
Now we just use induction. Without loss of generality m ≤ n and n ≥ 7. Now
F (m , n − 4) and F (m , 6) give F (m , n) by Claim D.
Nonorientable genus of Km,n : In a similar way can prove that Km,n has nonorientable
genus g(Km,n) = (m − 2)(n − 2)/2 .
Minimum genus of complete tripartite graphs
Use of diamond sums suggested by Kawarabayashi, Stephens and Zha [KSZ04]. Used by
Ellingham, Stephens and Zha [ESZ06] (together with transition graphs and surgical
techniques) to find nonorientable genus of all complete tripartite graphs.
Lower bound from Euler’s formulas, conjectured to give actual genus: assume ≥ m ≥ n:
g(K ,m,n ) ≥ ( − 2)(m + n − 2)/4 ,
g(K ,m,n ) ≥ ( − 2)(m + n − 2)/2 .
Note that lower bound is just genus of K ,m+n . So if this is really the genus, a min-
imum genus embedding of K ,m,n just consists of a minimum genus embedding of
K ,m+n with the edges of a Km,n inserted into the faces without changing the surface.
So diamond sum works in a way similar to complete bipartite graphs, but we have extra
edges of a Km,n on one side of the diamond sum. Specifically, we can take diamond
sum of K ,m,n with Kp,m+n , deleting vertex in first part of partition of each graph.
Result is K +p−2,m,n . Means that we can start with embeddings of K ,m,n for only a
small number of values of close to m (at worst m , m + 1 in nonorientable case or
m , m +1, m +2, m +3 in orientable case: stop at first value where no rounding occurs
in formula above) and then get all other values of by diamond sum.
Genus of families of graphs from hamilton cycle embeddings
The situation with complete tripartite graphs suggested looking at graphs that look like
complete bipartite graphs with some extra edges added on one side of the bipartition.
Turns out to be related to embeddings where all facial walks are hamilton cycles.
Claim B: F (3, 6) and F (4, 4) hold.
Proof:
Claim S: F (m , 6) holds for all m .
Proof: By repeated diamond sums with K3,6 we can build up K3,6 → K 4, 6 → K 5, 6 → . . .,
and since f 0(3, 6) = 1 is integral the result follows from Claim D.
Claim B+: F (m , n ) holds if m , n ≤ 6.
Proof: Use Claim S if m = 6 or n = 6. Claim B covers F (4, 4), and also F (3, 6) from which
we also get F (3, 3), F (3, 4) and F (3, 6). We get F (4, 5) from F (4, 6), and F (5, 5) from F (5, 6).
Now we just use induction. Without loss of generality m ≤ n and n ≥ 7. Now
F (m , n − 4) and F (m , 6) give F (m , n) by Claim D.
Nonorientable genus of Km,n : In a similar way can prove that Km,n has nonorientable
genus g(Km,n) = (m − 2)(n − 2)/2 .
Minimum genus of complete tripartite graphs
Use of diamond sums suggested by Kawarabayashi, Stephens and Zha [KSZ04]. Used by
Ellingham, Stephens and Zha [ESZ06] (together with transition graphs and surgical
techniques) to find nonorientable genus of all complete tripartite graphs.
Lower bound from Euler’s formulas, conjectured to give actual genus: assume ≥ m ≥ n:
g(K ,m,n ) ≥ ( − 2)(m + n − 2)/4 ,
g(K ,m,n ) ≥ ( − 2)(m + n − 2)/2 .
Note that lower bound is just genus of K ,m+n . So if this is really the genus, a min-
imum genus embedding of K ,m,n just consists of a minimum genus embedding of
K ,m+n with the edges of a Km,n inserted into the faces without changing the surface.
So diamond sum works in a way similar to complete bipartite graphs, but we have extra
edges of a Km,n on one side of the diamond sum. Specifically, we can take diamond
sum of K ,m,n with Kp,m+n , deleting vertex in first part of partition of each graph.
Result is K +p−2,m,n . Means that we can start with embeddings of K ,m,n for only a
small number of values of close to m (at worst m , m + 1 in nonorientable case or
m , m +1, m +2, m +3 in orientable case: stop at first value where no rounding occurs
in formula above) and then get all other values of by diamond sum.
Genus of families of graphs from hamilton cycle embeddings
The situation with complete tripartite graphs suggested looking at graphs that look like
complete bipartite graphs with some extra edges added on one side of the bipartition.
Turns out to be related to embeddings where all facial walks are hamilton cycles.
