[Translate to English:] Seminár z teórie grafov - Heidi Van den Camp (25.2.2021)
Thursday 25.2.2021 at 9:50
By: Martin Škoviera
Heidi Van den Camp (University of Ghent):
The Effect of Local Symmetry-Preserving Operations on the Connectivity of Embedded Graph
MS TEAMS code (users from Comenius University in Bratislava): gglxxc7
Link (guests outside Comenius University in Bratislava)
Symmetry-preserving operations on polyhedra have been studied for a very long time. However, it was only recently that a general description of all 'local symmetry-preserving operations' (lsp-operations) was presented. With this description it becomes possible to prove general results about all lsp-operations instead of studying every operation separately. We use this approach to investigate the effect of lsp-operations on the (3-)connectivity of embedded graphs.
Historically, symmetry-preserving operations have mostly been applied to polyhedra (3-connected plane graphs), but there is no mathematical reason why the new definition of lsp-operations could not be applied to more general embedded graphs. For plane graphs, all lsp-operations preserve 3-connectivity, but once we start looking at graphs with a higher genus this is no longer the case. The dual is the most striking example of an lsp-operation that can greatly reduce the connectivity of an embedded graph, but there are other operations that can destroy 3-connectivity in certain embedded graphs. We characterise exactly which lsp-operations always preserve 3-connectivity and which operations do not.