We are looking for graphs with certain properties that have a specific genus. We constructed a simple family, but now realised that we actually only have an upper bound for the genus. Is there an easy way to show that the genus is actually the desired value?

Take the cartesian product of two sufficiently large cycles (e.g., $C_{10}\times C_{10}$). This clearly has genus 1. Now imagine these graphs embedded on the torus, select a square in each embedded graph, and 'place' these two tori next to each other, aligning two squares. Then subdivided each edge of the two squares and connect corresponding edge centers in both squares. This graph clearly has genus at most 2 since we now have an embedding for the graph which is genus 2. Does there exist an embedding for this graph with a smaller genus? We can repeat this operation, forming a 'tower' of tori. Is there a simple argumentation that the genus of these graphs is indeed the number of constituent $C_{10}\times C_{10}$'s?

Related, if we would blow up each of the degree 4 vertices in these graphs to a cycle of length 4, can the genus decrease? We strongly feel that this cannot happen, but I'm not sufficiently familiar with the results in the field to give a quick argumentation.

  • $\begingroup$ I think your claims are all true, and that they can be shown using elementary arguments. I recommend reading Chapter 4 of Diestel's Graph Theory to get topological prerequisites and examples how to construct the kind of proofs you are looking for. $\endgroup$ – Puck Rombach Dec 21 '18 at 20:01

Since the genus is additive over connected components, it is sufficient to find $g$ vertex-disjoint subdivisions of $K_{3,3}$, one in each copy of $C_{10}\times C_{10}$. This will show that the genus of the whole graph is at least $g$. The same approach may be used after blowing-up the vertices into cycles.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.