Tomaž Pisanski, Construction of regular graphs with prescribed and prohibited cycle lengths

Let  be integer parameters. By G(k,N,g1,g2,...,gs) we denote the family of k-regular connected graphs that contain cycles of lengths g1,g2,...,gs but no other cycles of length < N. In this paper we give explicit construction of graphs from G(k,N,g1,g2,...,gs).

On the one hand this construction raises the quest for graphs with prescribed parameters having the least number of vertices. We call such graphs  \emph{generalized cages}. On the other hand bipartite graphs can be interpreted as Levi graphs of combinatorial configurations. Namely, if all values  are even, let  denote the family of bipartite graphs satisfying these conditions. A slight modification of our construction proves that the family B(k,N,g1,g2,...,gs) is nonempty. Encouraged by recent positive results for 3-configurations and N=12, a general question of the existence of geometric k-configurations of points and lines with prescribed and prohibited multilateral lengths is raised. Finally, the bipartite case allows a natural generalization form regular to semi-regular graphs.

(Joint work with Marko Boben and Robert Jajcay)