Workshop 2012 - Abstracts

# Abstracts

Klavidja Kutnar     —     Classification of symmetric Tabčjn graphs

Given natural numbers n >= 3 and 1 <= a, b, r <= n - 1, the Tabačjn graph T( n; a, b; r ) is a pentavalent graph with vertex set

 $\{ x_i \, | \, i \in \ZZ_n \} \cup \{ y_i \, | \, i \in \ZZ_n \}$

and edge set

 $\{ \{x_i,x_{i + 1}\} \mid i \in \ZZ_n \} \cup \{ \{y_i,y_{i + r}\} \mid i \in \ZZ_n \} \cup \{ \{x_i,y_i\} \mid i \in \ZZ_n \} \cup \{ \{x_{i},y_{i+a}\} \mid i \in \ZZ_n \} \cup \{ \{x_{i},y_{i+b}\} \mid i \in \ZZ_n \}$.

In this talk I will present a recent classification of symmetric Tabačjn graphs. This is a joint work with Aubin Arroyo, Adolfo Guillot, Isabel Hubard, Eugenia O'Reilly and Primož Šparl.

In this talk we consider the following problem: for a given class of groups {\cal G}, classify distance-regular Cayley graphs Cay(G; S), where G \in {\cal G}.

In 1984, Alspach conjectured that every 2k-regular connected Cayley graph on a finite Abelian group is decomposable into k Hamilton cycles. The method of lifting edge sets in quotient graphs to pseudo-cartesian products is used to obtain a useful representation of the graph upon which to perform edge color-switching. We outline new progress on the conjecture for the 6-regular Cayley graphs on Abelian groups of even order and list some open problems.

A matroid is a mathematical set system that is a common generalization of the concepts of a graph and of a projective geometry. Many important results in combinatorics deal with excluded-minor characterizations of classes of graphs and matroids. One famous example of such a result is Kuratowski’s Theorem which states that a graph is planar if and only if it is {K5, K3,3}-free. Guoli Ding and Cheng Liu have characterized many classes of graphs that are H-free for graphs H with fewer than twelve edges. We have extended some of their results to the class of regular 3-connected matroids.
Dillon Mayhew and Gordon Royle recently characterized the class of binary internally 4-connected matroids that are prism-free. As an extension of their result, we have determined the structure of the class of binary 3-connected matroids that are (prism + e)-free. We will also briefly discuss MACEK, a matroid computing program developed by Petr Hliněný that has proven to be particularly useful in our work in excluded-minor characterizations.

Vertex-decomposability is an important tool in topological combinatorics and combinatorial commutative algebra. Every matroid, for example, is vertex-decomposable. I'll give basic background, focused toward the independence complex of a graph Ind G. I'll discuss my classification of the minimal graphs such that Ind G is not vertex-decomposable. I'll close by stating recent results of Vander Meunier, Van Tuyl, and Watt concerning vertex-decomposability of Cayley graphs.