Maximal embedding genus of 3-edge connected harary graphs
No Thumbnail Available
Files
Date
2023
Journal Title
Journal ISSN
Volume Title
Publisher
Faculty of Science, University of Kelaniya Sri Lanka
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 H3,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 H3,n is given by for each n, by analysing the odd components of the complement of the corresponding spanning trees.
Description
Keywords
3-Edge connected graphs, Harary graph, Spanning tree, Upper-embeddability
Citation
Withanaarachchi W.A.K.D.H.; Almeida S.V.A.; Wijesiri G.S. (2023), Maximal embedding genus of 3-edge connected harary graphs, proceedings of the postgraduate institute of Science Research Congress, postgraduate institute of Science Research Congress, Sri Lanka,