Collaborative Research: Graphs on Surfaces and Related Problems

Vanderbilt University, Nashville TN

Investigators

Abstract

Collaborative Research: Graphs on Surfaces and Related Problems Mark N. Ellingham and Xiaoya Zha The investigators study properties of graphs embedded on surfaces, together with some closely related problems. The proposed research addresses five types of problems. First, traversability problems for graphs embedded on surfaces, or with related conditions, are studied. In particular, the existence of k-walks and k-trails, ways to traverse a graph visiting each vertex at least once and at most k times, are investigated. Second, the investigators study the spectral radius (largest eigenvalue of the adjacency matrix) of graphs embedded on surfaces, particularly the plane; this is an important parameter with connections to the number of walks in the graph. Third, the investigators examine the relationship between a surface and the connectivity of graphs that embed on that surface in particularly natural ways, as genus embeddings. Fourth, the existence of graph embeddings with nice properties, such as every closed face being homeomorphic to a closed disk, and the relationship of such embeddings to decomposition problems such as the Cycle Double Cover Conjecture, are studied. Fifth, the investigators are concerned with the problem of cutting a surface with an embedded graph into smaller nontrivial pieces along a noncontractible cycle in the graph, as results in this area would give a very promising tool for studying many problems in the area of graph embeddings. Graphs are abstract mathematical models of networks. In the modern world, the study of communication and transportation networks is becoming ever more important. In particular, many real-world networks are planar, meaning that they can be drawn on a piece of paper without any links crossing. How close a network is to being planar is related to many of its useful properties, and mathematicians study this by looking at so called embeddings of graphs on surfaces. The useful properties examined by this research include traversability (how can we travel around a network, visiting each node, in a more or less efficient way - this is the motivation for such problems as the Traveling Salesman Problem), how well a network works as a traffic network (this involves a number known as the spectral radius, which has been of interest to geographers), and connectivity (resistance to disruption by attack). Besides studying the useful properties of networks, this research also develops new tools for studying such properties. Networks drawn on a surface are easier to work with if none of the regions into which the drawing divides the surface touch themselves, and the investigators are interested in the question of whether networks can always be drawn in this nice way. The investigators are also interested in the question of whether networks drawn on a surface can be cut apart in a natural way to give networks drawn on less complicated surfaces. Both of these questions should lead to better understanding of networks drawn on surfaces, and hence to ways to examine useful properties of such networks.