Tomaž Pisanski: Seminar za diskretno matematiko 15.12.2009

Iz MaFiRaWiki

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)

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja