2019/06/18 by Marston Conder, Klara Stokes · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Genomics and Chromatin Dynamics #Advanced Graph Theory Research #Protein Degradation and Inhibitors #Mathematics #Combinatorics #Genus #Biology #Botany
paper · pdf · doi:10.26493/1855-3974.1800.40c
published in Ars Mathematica Contemporanea 17(1), 1-35 (Society of Mathematicians, Physicists and Astronomers of Slovenia)
openalex publication_date 2019/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/27
The question of how to find the smallest genus of all embeddings of a given finite connected graph on an orientable (or non-orientable) surface has a long and interesting history. In this paper we introduce four new approaches to help answer this question, in both the orientable and non-orientable cases. One approach involves taking orbits of subgroups of the automorphism group on cycles of particular lengths in the graph as candidates for subsets of the faces of an embedding. Another uses properties of an auxiliary graph defined in terms of compatibility of these cycles. We also present two methods that make use of integer linear programming, to help determine bounds for the minimum genus, and to find minimum genus embeddings. This work was motivated by the problem of finding the minimum genus of the Hoffman-Singleton graph, and succeeded not only in solving that problem but also in answering several other open questions.