Conder, Marston and Stokes, Klara (2019) New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces. Ars Mathematica Contemporanea, 17 (1). pp. 1-35. ISSN 1855-3966

Preview

Download (434kB) | Preview

Abstract

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.

Item Type:	Article
Additional Information:	This work is licensed under https://creativecommons.org/licenses/by/4.0/
Keywords:	Graph embedding; genus;
Academic Unit:	Faculty of Science and Engineering > Electronic Engineering
Item ID:	14074
Identification Number:	https://doi.org/10.26493/1855-3974.1800.40c
Depositing User:	Klara Stokes
Date Deposited:	24 Feb 2021 17:41
Journal or Publication Title:	Ars Mathematica Contemporanea
Publisher:	Society of Mathematics, Physicists and Astronomers of Slovenia
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads