A quadrangular embedding of a complete graph is a minimal (smallest order) quadrangulation of a surface. Divisibility conditions based on Euler’s formula give necessary conditions for such embeddings to exist. In 1989 Hartsfield and Ringel showed that quadrangular complete graph embeddings exist in half of the possible cases. We show existence in the remaining cases. In the orientable case we use the ‘graphical surface’ technique due to Craft, combined with voltage graphs. In the nonorientable case we use the ‘diamond sum’ techique originally due to Bouchet. Both results were apparently also proved, but never published, in the 1990s by Chen, Lawrencenko and Yang (orientable case, using current graphs) and Hartsfield (nonorientable case). Our techniques also yield some results on minimal quadrangulations where the graph is not a complete graph.
This is joint work with Wenzhong Liu, Dong Ye and Xiaoya Zha.
Path-pairability is a graph theoretical notion that emerged from a practical networking problem introduced by Csaba, Faudree, Gyárfás, Lehel, and Schelp, and further studied by Faudree, Gyárfás, and Lehel; and by Kubicka, Kubicki and Lehel. A graph is path-pairable if for any pairing of its vertices there exist edge disjoint paths joining the vertices in each pair. One central question in path-pairability is how small can be the maximum degree of a path-pairable graph. Faudree, Gyárfás, and Lehel showed that a path-pairable graph on n vertices has maximum degree at least log n / loglog n. To date the best known constructions are due to Győri, Mezei, and Mészáros, and they offer examples of path-pairable graphs with maximum degree c · log n. In my talk I will summarize the evolution of the topic, present the latest known results, and discuss possible directions of future research.