Raziskovalni matematični seminar - Arhiv

A bicirculant is a graph admitting an automorphism with two cycles of equal length in its cycle decomposition. A graph is said to be arc-transitive if its automorphism group acts transitively on the set of arcs of the graph.

In this talk I will present a classification of pentavalent arc-transitive bicirculants.

This is a joint work with Iva Antončič and Klavdija Kutnar.

We study $1$-codes in distance-regular graphs of diameter $3$ that achieve three different bounds. We show that the intersection array of a distance-regular graph containing such a code has the form$\{a(p+1), cp, a+1; 1, c, a p\}$ or $\{a(p+1), (a+1)p, c; 1, c, a p\}$ for $c=c_2$, $a=a_3$ and $p=p_{33}^3$. These two families contain$10+15$ known feasible intersection arrays out of which four are uniquely realized by the Sylvester graph, the Hamming graph $H(3,3)$, the Doro graph and the Johnson graph $J(9,3)$, but not all members of these two families are feasible. We construct four new one-parameter infinite subfamilies of feasible intersection arrays, two of which havea nontrivial vanishing Krein parameter:$\{(2r^2-1)(2r+1), 4r(r^2-1), 2r^2; 1, 2(r^2-1), r(4r^2-2)\}$ and $\{2r^2(2r+1), (2r-1)(2r^2+r+1), 2r^2; 1, 2r^2, r(4r^2-1)\}$ for $r > 1$ (the second family actually generalizes to a two-parameter family with the same property).Using this information we calculate some triple intersection numbers for these two families to show that they must contain the desired code. Finally, we use some additional combinatorial arguments to prove nonexistence of distance-regular graphs with such intersection arrays.

Slides from the talk are available here: DOWNLOAD SLIDES!

The Cayley polytope was defined recently as the convex hull of Cayley compositions, introduced by Cayley in 1857. In this talk, I will describe how we resolved Braun's conjecture, which expresses the volume of the Cayley polytope in terms of the number of connected graphs. We extend this result to a two-variable deformation, which we call the Tutte polytope. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph. Our approach is based on an explicit triangulation of the Cayley and Tuttepolytopes. We prove that simplices in the triangulations correspond to labeled trees. The heart of the proof is a direct bijection based onthe neighbors-first search graph traversal algorithm.

The slides from the talk are available here: DOWNLOAD SLIDES!