KPPY 91

I will discuss what has been done and left to be done after the monumental paper of Terwilliger: The Subconstituent Algebra of an Association scheme I, II, III.

TBA

In this talk we discuss hamiltonian problem on Cayley graphs. In particular, we present an approach for constructing hamiltonian cycles in Cayley graphs over the symmetric group. This aproach is based on cyclic coverings of graphs and algebraic operations with them. This is joint work with Alexey Medvedev, Universite de Namur, Belgium.

For a graph $G$, let $f_2(G)$ denote the largest number of vertices in a $2$-regular subgraph of $G$. We determine the minimum of $f_2(G)$ over $3$-regular $n$-vertex simple graphs $G$. To do this, we prove that every $3$-regular multigraph with exactly $c$ cut-edges has a $2$-regular subgraph that omits at most $\max\{0,\lfloor (c-1)/2\rfloor\}$ vertices. More generally, every $n$-vertex multigraph with maximum degree $3$ and $m$ edges has a $2$-regular subgraph that omits at most $\max\{0,\lfloor (3n-2m+c-1)/2\rfloor\}$ vertices. These bounds are sharp; we describe the extremal multigraphs. This is joint work with R. Kim, A. Kostochka, B. Park, and D. B. West.