Maximal embedding genus of 3-edge connected Harary graphs

Abstract

One of the most prominent problems of topological graph theory is to determine the type of surface a nonplanar graph can be embedded. Almost complete results have been obtained for 4-edge connected graphs. The methods that were used to obtain specific results (finding the maximum and minimum genus embedding) for 4-edge connected graphs do not generalise for 3-edge connected graphs. Graph embedding is an important representational technique that aims to maintain the structure of a graph while learning low-dimensional representations of its vertices. The aim of this research project was to study the embedding of 3-edge connected Harary graphs H₃,n. Specifically to complete the problem of maximal embeddings of 3-edge connected Harary graphs. The result is proved using Jungerman’s study, which showed that for any graph 𝐺, 𝐺 is upper-embeddable if and only if it has a spanning tree T such that 𝐺 ∖ 𝑇 has at most one component with an odd number of edges. More specifically, a spanning tree for each graph was observed by dividing all 3-edge connected Harary graphs into two groups: odd number of vertices and even number of vertices. The pattern of a set of deleting edges and corresponding spanning trees was generalised in both cases. It was proved that H3,n is upper-embeddable, and the maximum genus of H₃,n is given by 𝛾𝑀 (𝐻3,𝑛) = ⌊ (2+𝑛) /4 ⌋ for each n, by analysing the odd components of the complement of the corresponding spanning trees.