Discrete Math Seminar Fall 2008
Some Problems on Graph Subdivisions
Mike Ferrara, University of Akron;
Colloquium on Fri Oct 3
Broadly, structural graph theory is concerned with ensuring or prohibiting the presence of certain substructures within a graph. The most prevalent results of this type in the literature deal with the existence of paths and cycles having a wide variety of properties. A "subdivision" of a graph H is any graph obtained by replacing the edges of H with paths of arbitrary length. It is not difficult to see that if H is a path or a cycle, then so too is any subdivision of H. With this observation in mind, it is not surprising that many results that ensure the existence of an arbitrary H-subdivision extend known results pertaining to paths and cycles.
We will discuss two classes of problems related to H-subdivisions. First, we will introduce the notion of an H-linked graph, which extends several concepts including k-linked, k-ordered and k-connected graphs. We will then discuss conditions that assure the existence of H-subdivisions of many different sizes in a graph, and use our results to draw several parallels to pancyclicity and panconnectivity.