Topological Operations for Genus Distributions and Embeddings of Graphs

The research of graph embeddings on surfaces started from Euler's equation v e+f = 2. For a connected graph G, v, e and f represent the number of vertices, edges and regions of an embedding on a plane or sphere. Genus embedding of graphs is one of the most studied subjects in topological graph theory. A polynomial is used to represent a graph's embedding distribution on di erent surfaces which are classi ed by genus. We discuss orientable genus embeddings of connected undirected graphs which are derived from some other graphs by topological operations, including face-contraction, vertexsplitting, vertex-augment, pearl-making, bouquet-making and face-expansion which are designed to treat one graph. We then consider the Cartesian product, dot product and extended dot product which are designed to be applied between two graphs. Face-contraction, vertex-splitting, vertex-augment, pearl-making, bouquet-making and face-expansion are discussed to achieve partial genus distribution of some graphs, including fan graph Fn, cube-connected cycles CCCn and star-connected cycles SCCn. For several in nite families of graphs, we calculate their minimum and maximum genus and demonstrate constructions of embeddings of all genera between these ranges. The graphs discussed in the thesis are derived from Cartesian product, dot product and a newly de ned extended dot product.

Name thesis:degree_name

PhD

Level thesis:degree_level

Doctoral

Grantor dc:publisher

ResearchSpace@Auckland

Year dc:date.issued

2012

Author dc:creator

• Zhu, Zilong

Advisors dc:contributor.advisor

• Sneddon, J
• Conder, M

Statement dc:rights

• Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.

Licence dc:rights.uri

• https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

Handle dc:identifier.uri

https://hdl.handle.net/2292/20625

OAI identifier oai:identifier

oai:researchspace.auckland.ac.nz:2292/20625