Tomaž Pisanski: Seminar za diskretno matematiko 15.12.2009

Construction of regular graphs with prescribed and prohibited cycle lengths

Tomaž Pisanski, IMFM

Let $k \geq 3 , 3 \leq g_1 < g_2 < \ldots < g_s < N$ be integer parameters. By $G(k,N,g_1,g_2,\ldots,g_s)$ we denote the family of k-regular connected graphs that contain cycles of lengths $g_1, g_2, \ldots, g_s$ but no other cycles of length < N. In this paper we give explicit construction of graphs from $G(k,N,g_1,g_2,\ldots,g_s)$.

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 $g_i, 1 \leq i \leq s$ are even, let $B(k,N,g_1,g_2,\ldots,g_s) \subset G(k,N,g_1,g_2,\ldots,g_s)$ denote the family of bipartite graphs satisfying these conditions. A slight modification of our construction proves that the family $B(k,N,g_1,g_2,\ldots,g_s)$ 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)