Longest Cycles and Spanning Subgraphs

The main themes of this research project, which is situated in Graph Theory, are the study of longest cycles and of spanning subgraphs of abstract and embedded graphs. A subgraph is "spanning" if it contains all vertices of the supergraph. Special emphasis will lie on hamiltonian cycles, i.e. spanning cycles, and their interaction with other important structural properties of the graph such as its genus, crossing number, connectivity, and toughness. The former two measure how far a graph is from being planar (a setting one might consider as the most natural one), while the latter two indicate how tightly it holds together. The central directions of research in this proposal, in part to be carried out in collaboration with German, Hungarian, Japanese, Slovakian, and South African graph theorists, will be to study • extensions of a theorem of Thomassen on the hamiltonicity of a graph and its vertex-deleted subgraphs; • Grünbaum's problem on longest cycles avoiding any pair of vertices and a related question of Katona, Kostochka, Pach, and Stechkin; • hamiltonicity in 3-connected graphs with few cuts and crossings; • the shortness exponent, a limit introduced by Grünbaum and Walther to measure the circumference of graphs from a given family of graphs; • the Path Partition Conjecture for directed graphs; • planarising 2-factors -- natural extensions of plane hamiltonian cycles to graphs on higher surfaces; and • spanning trees with few leaves and a criticality notion.