Abstracts

 

Automorphism Groups of Planar Graphs  submitted by  Peter Zeman
Roman Nedela; Pavel Klavík; Peter Zeman

In 1975, Babai characterized which abstract groups can be realized as the automorphism groups of planar graphs. In this paper, we give a more detailed and understandable description of these groups. We describe stabilizers of vertices in connected planar graphs as the class of groups closed under the direct product and semidirect products with symmetric, dihedral and cyclic groups. The automorphism group of a connected planar graph is then obtained as a semidirect product of a direct product of these stabilizers with a spherical group. The formulation of the main result is new and original. Moreover, it gives a deeper in the structure of the groups. As a consequence, automorphism groups of several subclasses of planar graphs, including 2-connected planar, outerplanar, and series-parallel graphs, are characterized. Our approach translates into a quadratic-time algorithm for computing the automorphism group of a planar graph which is the first such algorithm described in detail.

 

Balanced subdivisions and flips on surfaces  submitted by  Yusuke Suzuki
Yusuke Suzuki; Satoshi Murai

In this talk, we show that two balanced (i.e., 3-colorable) triangulations of a closed surface are not necessary connected by a sequence of balanced stellar subdivisions and welds. This answers a question posed by Izmestiev, Klee and Novik. We also show that two balanced triangulations of a closed surface are connected by a sequence of three local operations, which we call the pentagon contraction, the balanced edge subdivision and the balanced edge weld. In addition, we prove that two balanced triangulations of the sphere are connected by a sequence of pentagon contractions and their inverses if none of them is isomorphic to the octahedron.

 

Bipartite-regular hypermaps  submitted by  Rui Duarte
Rui Duarte

A hypermap is \emph{bipartite} if its set of flags can be divided into two parts $A$ and $B$ so that both $A$ and $B$ are the union of vertices, and consecutive vertices around an edge or a face are contained in alternate parts. A bipartite hypermap is \emph{bipartite-regular} if its set of automorphisms is transitive on both $A$ and $B$. In this talk we present some properties of bipartite-regular hypermaps, as well as their classification on surfaces of small genus.

 

Classification of regular Cayley maps for dihedral groups  submitted by  Young Soo Kwon
Young Soo Kwon, Istvan Kovacs

A regular map is a 2-cell embedding of a connected graph into an orientable surface such that the group of all orientation-preserving automorphisms of the embedding acts transitively on the set of all incident vertex-edge pairs called arcs. Such a map M is called a regular Cayley map for the finite group G if M is an embedding of a Cayley graph C(G,S) such that G induces a vertex-transitive group of map automorphisms preserving orientation. In this talk, we consider the classification of all regular Cayley maps for dihedral groups.

 

Correlation among triad colorings of triangulations on closed surfaces  submitted by  Yumiko Ohno
Yumiko Ohno

Let $G$ be a triangulation on a closed surface. A coloring $c : V(G) \to \mathbb{Z}_n$ is called an $n$-triad coloring if $\{c(u), c(v), c(w)\}$ belongs to $\{\{i, i+1, i+2\} \mid i \in \mathbb{Z}_n\}$ for any face $uvw$ of $G$. We discuss the number of colors $n$ such that $G$ has $n$-triad colorings. In particular, we shall show that if $G$ has an $n$-triad coloring for $n \ge 6$, then it has a 4-triad coloring and it has $m$-triad colorings with $m \mid n$.

 

Cubic arc-transitive $k$-multicirculants.  submitted by  Michael Giudici
Michael Giudici

Given a positive integer $k$, a $k$-multicirculant is a graph that admits an automorphism whose cycle decomposition consists of precisely $k$ cycles, all of the same length. All cubic arc-transitive $k$-multicirculants with $k\leq 5$ have been classified by various authors. For $k=1,3$ and 5 there are finitely many, while for $k=2$ and $4$ there are infinitely many. In this talk I will discuss recent work with István Kovács, Cai Heng Li and Gabriel Verret that investigates for arbitrary values of $k$, when are there infinitely many cubic arc-transitive $k$-multicirculants and when are there only finitely many.

 

Cubic vertex-transitive graphs of small girth  submitted by  Primoz Potocnik
Janoš Vidali

A database of all cubic vertex-transitive graphs of order up to 1280 suggests that those having small girth must have a very special structure. In this paper, I will discuss a recent result about cubic vertex-transitive graphs of girth at most 6. I will also introduce a concept of a girth-regularity of a graph that generalises the classical notions of vertex-transitivity and distance-regularity, as well as a more recent notion of girth-edge-regularity introduced by Robert Jajcay and Štefko Miklavič.

 

Digraphs that are Cayley for two non-isomorphic groups  submitted by  Luke Morgan
Joy Morris; Gabriel Verret

Let $p$ be an odd prime and let $\Gamma=\mathrm{Cay}(G,S)$ be a Cayley digraph on a cyclic $p$-group $G$. A result of Morris shows that if $\Gamma$ is Cayley on another non-isomorphic group, then $\Gamma$ has large Cayley index with respect to $|G|$. Here, Cayley index refers to $|\mathrm{Aut}(\Gamma) : G |$, or equivalently, the size of a vertex stabiliser in $\mathrm{Aut}(\Gamma)$. I'll describe a recent joint work with Joy Morris and Gabriel Verret in which we showed that cyclic groups may be exceptional in this respect. That is, we showed that for a non-cyclic abelian $p$-group $P$ of order at least $p^3$, there is a Cayley digraph $\Gamma$ on $P$ that is Cayley on another non-isomorphic group with Cayley index $p$ (as small as possible).

 

Directed strongly regular graphs and voltage assignments  submitted by  Stefan Gyurki
Štefan Gyürki

A directed strongly regular graph (DSRG) with parameters $(n,k,t,\lambda,\mu)$ is a $k$-regular directed graph of order $n$ such that every vertex is incident with $t$ undirected edges; the number of directed paths of length 2 directed from a vertex $x$ to another vertex $y$ is $\lambda$, if there is an arc from $x$ to $y$ and $\mu$ otherwise. In the talk we investigate relations of DSRGs to the technique of voltage assignments. The author gratefully acknowledges the contribution of the Scientific Grant Agency of the Slovak Republic under the grant 1/0988/16, as well as the constribution of the Slovak Research and Development Agency under the projects APVV 0136-12 and APVV 0220-15.

 

Distinguishing Graphs of Maximum Valence 3  submitted by  Thomas W. Tucker
Thomas Tucker, Wilfried Imrich, Svenja H\"uning, Judith Kloas and Hannah Schreiber

The finite or infinite connected graph $G$ with maximum valence $d>2$ has distinguishing number $D(G)=k$ if the vertices have a $k$-coloring which is preserved only by the identity automorphism, and there is no smaller such $k$. In general, the ``generic case" is $D(G)\leq 2$ for large classes of graphs. For finite $G$, Collins and Trenk (2006) showed, $D(G)\leq d+1$ with equality only for $K_{d+1}$ and $K_{d,d}$; for infinite $G$, Imrich, Klav\v zar and Trofimov (2007) showed $D(G)\leq d$.. Define the tree $T_{n,d}$ for $n>0$ to have all vertices of valence $1$ or $d$ and every leaf the same distance $n$ from the vertex $v$. Clearly, $D(T_{n,d})=d$. For $d=3$, we show that $D(G)=3$ only for the cube, the Petersen graph, $K_{2,3}$, the trees $T_{n,3}$, and four other families obtained from from $T_{n,3}$ by adding ``gadgets" between sibling pairs of leaves. In particular, $D(G)\leq 2$ for all infinite graphs with $d=3$.

 

Doubly Hurwitz Beauville groups  submitted by  Gareth Aneurin Jones
Gareth A. Jones

In algebraic geometry, a Beauville surface $S$ is a 2-dimensional complex variety, formed (for the purposes of this conference) from a pair of orientably regular hypermaps of genus greater than 1, with the same automorphism group $G$ (called a Beauville group) acting freely on their product. The well-known Hurwitz bound implies that the Euler characteristic of $S$ is at least $|G|/1764$, attained if and only if the two hypermaps have type (2,3,7), i.e. they can be regarded as Hurwitz maps. The requirement that $G$ should act freely on the product is equivalent to none of the generators in one generating triple for $G$ being conjugate to a power of a generator in the other triple. Although many families of Hurwitz groups are known, there are no such doubly Hurwitz examples among the sporadic simple groups or the simple groups of low rank. However if $n$ is sufficiently large then the alternating groups $A_n$, their double covers $2.A_n$ and the special linear groups $SL_n(q)$ all have this property. (This is work in progress with Emilio Pierro.)

 

Edge-transitive oriented graphs of valency four: quotients and cycles  submitted by  Cheryl E. Praeger
Cheryl E. Praeger, Jehan Al-bar, Ahmad Kenani and Najat Muthana

I will report on our analysis of the structure of this family of oriented graphs in terms of their quotients – especially their cyclic normal quotients. Our approach gives new insights, and makes possible various classifications. For example, each example with independent cyclic normal quotients is shown to be a normal cover of a graph from one of five explicit families. Graphs from most of these five families had previously been used in the literature to illustrate various local properties. This new quotient approach highlights their importance. There are several open problems which I’ll mention.

 

Equivariant orbits of spherical groups acting on polyhedra  submitted by  Roman Nedela
Roman Nedela, Peter Zeman

We investigate of the action of automorphism groups of polyhedra on vertices and edges. It is well-known that the authomorphisms groups of polyhedra are the spherical groups. For each (parametrised) spherical group we first determine the equivariance classes of point-orbits. Then we shall determine possible lengths of orbits on vertices and edges of a polyhedron up to equivalence relation given by equivariance. The motivation comes from investigation of the structure of groups of automorphisms of planar graphs.

 

Facial list colourings of plane graphs  submitted by  Stanislav Jendrol
Igor Fabrici; Stanislav Jendroľ; Margit Voigt

Let $G=(V,E,F)$ be a connected plane graph, with vertex set $V$, edge set $E$, and face set $F$. For $X\in\{V,E,F,V\cup E,V\cup F,E\cup F, V\cup E\cup F\}$, two distinct elements of $X$ are facially adjacent in $G$ if they are incident elements, adjacent vertices, adjacent faces, or facially adjacent edges (edges that are consecutive on the boundary walk of a face of $G$). A list $k$-colouring is facial with respect to $X$ if there is a list $k$-colouring of elements of $X$ such that facially adjacent elements of $X$ receive different colours. We prove that every plane graph $G=(V,E,F)$ has a facial list 4-colouring with respect to $X=E$, a facial list 6-colouring with respect to $X\in\{V\cup E,E\cup F\}$, and a facial list 8-colouring with respect to $X=V\cup E\cup F$. For plane triangulations, each of these results is improved by one and it is tight. These results complete the theorem of Thomassen that every plane graph has a (facial) list 5-colouring with respect to $X\in\{V,F\}$ and the theorem of Wang and Lih that every simple plane graph has a (facial) list 7-colouring with respect to $X=V\cup F$.

 

Fano plane’s embeddings on compact orientable surfaces  submitted by  Domenico Antonino Catalano
Domenico Catalano and Cristina Sarti

In this talk, we show a way of classifying embeddings of projective spaces on compact orientable surfaces taking the Fano plane as an example. We give all quotients of Fano plane's embeddings with non-trivial automorphism group and show how to obtain information about face structure and genus of the embedding.

 

Generalized hexagons and degree-diameter problem for diameter 4  submitted by  Martin Bachraty
Martin Bachratý, Jana Šiagiová, Jozef Širáň

The largest order $n(d,k)$ of a graph of maximum degree $d$ and diameter $k$ cannot exceed the Moore bound, which has the form $M(d,k)=d^k - O(d^{k-1})$ for $d\to\infty$ and any fixed $k$. Known results in finite geometry on generalized $(k+1)$-gons admitting a polarity imply, for $k=2,3,5$, the existence of an infinite sequence of values of $d$ such that $n(d,k)=d^k - o(d^k)$. This shows that for $k=2,3,5$ the Moore bound can be asymptotically approached in the sense that $\liminf_{d\to\infty}{n(d,k)/M(d,k)} = 1$; moreover, no such result is known for any other value of $k\ge 2$. The main aim of this talk is to show how known results on generalized hexagons admitting polarity might also help us in construction of large graphs of given maximum degree $d$ and diameter $4$.

 

Kernel-preserving skew-morphisms  submitted by  Kan Hu
Kan Hu

A permutation $\varphi$ of a finite group of $A$ is called a skew-morphism of $A$ if $\varphi(1)=1$ and there is an integer function $\pi:A\to\mathbb{Z}_n$ such that $\varphi(xy)=\varphi(x)\varphi^{\pi(x)}(y)$ for all $x,y\in A$ where $n=|\varphi|$ is the order of $\varphi$. The kernel of $\varphi$ is the subgroup $\mathrm{Ker}\,\varphi=\{x\in A\mid \pi(x)\equiv 1\pmod{n}\}$, and the core of $\varphi$ is the normal subgroup $ \mathrm{Core}\,\varphi=\bigcap_{i=1}^n\varphi^i(\mathrm{Ker}\,\varphi).$ A skew-morphism $\varphi$ of $A$ will be called stable if $\varphi(x)\equiv x\pmod{\mathrm{Core}\,\varphi}$ for all $x,y\in A$, and kernel-preserving if $\varphi(\mathrm{Ker}\,\varphi)=\mathrm{Ker}\,\varphi$. A stable kernel-preserving skew-morphism will be called smooth (or coset-preserving). In this talk we present some observations on such particular classes of skew-morphisms.

 

Link indices of regular maps  submitted by  Adnan Melekoglu
Adnan Melekoglu

Let $\mathcal{M}$ be a reflexible regular map of type $\{m,n\}$ on a compact Riemann surface $X$. We can associate with $\mathcal{M}$ one, two or three positive integers depending on the parity of $m$ and $n$. These integers are the orders of particular kinds of conformal automorphisms of $\mathcal{M}$ and they are called the link indices of $\mathcal{M}$. In this talk I will describe the concept of link index and discuss its applications to the numbers and lengths of simple closed geodesics on $X$ fixed by the reflections of $\mathcal{M}$.

 

Maniplexes and the 2-orbit problem  submitted by  Micael Alexi Toledo
Daniel Pellicer, Primoz Potocnik, Micael Toledo

A maniplex of rank $n$, $\mathcal{M}$, is a connected, $n$-valent, edge-coloured graph that generalizes abstract polytopes and maps. If $Aut(\mathcal{M})$ partitions the vertex-set of $\mathcal{M}$ into $k$ distinct orbits, we say that $\mathcal{M}$ is a $k$-orbit maniplex. We define the symmetry type graph of $\mathcal{M}$ as the quotient pre-graph obtained by contracting every orbit into a single vertex. Symmetry type graphs of maniplexes have a series of very specific properties. The question arises whether any graph of order $k$ having these properties is the symmetry type graph of some $k$-orbit maniplex. We answer the question when $k = 2$.

 

On 3-edge colorability of bi-Cayley graphs  submitted by  Istvan Estelyi
István Estélyi, Roman Nedela

Bi-Cayley graphs are graphs admitting a semiregular group of automorphisms with two orbits. A notable cubic subclass of bi-Cayley graphs is the so-called generalized Petersen graphs. Castagna and Prins proved in 1972 that all generalized Petersen graphs except for the Petersen graph itself can be properly 3-edge-colored. In this talk we are going to discuss the extension of this result to all connected cubic bi-Cayley graphs over solvable groups. Our theorem is a bi-Cayley analogue of the similar result obtained by Nedela and Škoviera for Cayley graphs.

 

On arc-transitive maps   submitted by  Alejandra Ramos Rivera
Alejandra Ramos Riviera, Isabel Hubard, and Primož Šparl

In this talk we focus on arc-transitive maps, that is maps for which their automorphism group is arc-transitive on the its underlying graph. Of course, reflexible maps are examples of arc-transitive maps. As for maps $\mathcal{M}$, for which $Aut(\mathcal{M})$ has two orbits on the set of its flags, there are seven classes of such maps and only four of them result in arc-transitive maps; the corresponding classes are denoted by $2$, $2_0$, $2_1$ and $2_{0,1}$. The reflexible maps and maps in class $2$ (chiral maps) have been extensively studied in the literature. Moreover, the maps in class $2_0$ are related to the chiral ones via the Petrie operator (and their underlying graphs are the same). This leaves us with the maps of classes $2_1$ and $2_{0,1}$ which are also related via the Petrie operator. It is known that the smallest admissible valency of the underlying graph of a map in class $2_{0,1}$ is four. It thus seems natural to first study maps of class $2_{0,1}$ with tetravalent underlying graphs. In 2008 S. Wilson introduced a family of tetravalent graphs now known as the Rose Window graphs and identified four families of arc-transitive members. The reflexible maps and maps in class $2$ (and so in class $2_1$) underlying these graphs were classified by I. Kovács, K. Kutnar and J. Ruff. In this talk we classify all maps in class $2_{0,1}$ (and so in class $2_0$) underlying a Rose Window graph.

 

On minimal kaleidoscopic regular maps with trinity symmetry  submitted by  Martin Macaj
Martin Mačaj

It is known that the monodromy group of any regular unoriented map ${\cal M}$ can be uniquely (up to isomorphism) represented as an abstract group $G$ with a triple $(a,b,c)$ of involutory generators such that $ac=ca$. In this representation operators of duality, Petrie-duality and $e$th-hole operator can be interpreted as the change of the generating triple to the triple $(c,b,a)$, $(ac,b,c)$ and $(a,(bc)^{e-1}b,c)$, respectively. Regular map $M$ which is invariant with respect to all of the above operators (for $e$ co-prime to the valency of $M$) is said to be {\em kaleidoscopic regular map with trinity symmetry (KRT)}. We say that a KRT is {\em minimal} if it covers no KRT besides itself and the trivial map. In this talk we characterize minimal KRTs as least common covers of special families of regular maps with simple monodromy groups. We also presents results of exhaustive computer search with focus on KRTs of odd valency and KRTs with simple monodromy groups.

 

Regular Embeddings of the Praeger-Xu Graphs  submitted by  Steve Wilson
Robert Jajcay, Primoz. Potocnik, Steve Wilson

The graph $PX(n,k)$ is the tetravalent case of a family $C(m,n,k)$ introduced by C. Praeger and M.-Y. Xu in 1989. They are exceptional for having very large symmetry groups with respect to order of the graph. In this talk, we use aspects of coding theory to determine which rotary maps have $PX$ graphs as their skeletons.

 

Skeletal Polygonal Complexes, Crystallographic Groups, and Symmetry  submitted by  Egon Schulte
Egon Schulte

Skeletal polygonal complexes in ordinary Euclidean 3-space are discrete geometric structures made up of finite (planar or skew) or infinite (helical or zigzag) polygons as faces, with two or more faces on each edge. Skeletal polyhedra are polygonal complexes with exactly two faces on each edge. These structures are viewed not as solids but rather as geometric edge graphs equipped with additional polyhedral super-structure imposed by the faces. We discuss the present state of the ongoing program to classify skeletal polygonal complexes by symmetry, where the degree of symmetry is defined via distinguished transitivity properties of the symmetry groups. A complete classification is known for the regular polygonal complexes (including regular polyhedra) and for the chiral polyhedra. There has also been recent progress on uniform (Archimedean) skeletal polyhedra. Remarkable new structures were discovered using a skeletal variant of Wythoff's construction in space.

 

Some new perspectives on finding minimum genus embeddings  submitted by  Marston D.E. Conder
Marston Conder and Klara Stokes

In 2014 we found the minimum genus embeddings of the Hoffman-Singleton graph, in both the orientable and non-orientable cases. When doing this, we found that traditional methods were not particularly helpful, so we had to develop a new approach (using orbits of the automorphism group on cycles of small length as candidates for faces of the embedding). I will describe how this approach turned out to be helpful in finding small genus embeddings of several other graphs, and then in combination with some other new approaches for eliminating smaller genera, enabled us to answer a number of open questions.

 

Stable embeddings of graphs on closed surfaces with minimum length  submitted by  Seiya Negami

We embed a graph $G$ on a closed surface having some metric and consider the total sum of lengths of edges measured by the metric. Such an embedding of $G$ is said to be {\em stable} if any sequence of embeddings of $G$ on the surface isotopic to its original embedding and whose total lengths decrease is convergent to an embedding of $G$ yet. We shall show some examples of stable embeddings on the torus and discuss a topology over the set of embeddings which makes our argument on the convergence consistent.

 

The classification of the oriented regular representations  submitted by  Pablo Spiga
Pablo Spiga

This talk is divided into two parts. First we aim to give a partial answer to a 1980 question of Lazslo Babai: ``Which [finite] groups admit an oriented graph as a DRR?" That is, which finite groups admit an oriented regular representation (ORR)? We show that every finite non-solvable group admits an ORR, and provide a tool that may prove useful in showing that some families of finite solvable groups admit ORRs. Then, we use this tool, to reduce the classification of the ORRs to the finite 2-groups. In the second part of this talk, we address another widely open question of Babai: asymptotic enumeration of Cayley (di)graphs.

 

Tiling of Sphere by Congruent Pentagons  submitted by  Min Yan
Yohji Akama, Hoiping Luk, Erxiao Wang, Min Yan

In 2002, Ueno and Agaoka completed the classification of edge-to-edge tilings of sphere by congruent triangles. We try to classify tilings by congruent pentagons. In GEMS2013, I presented our preliminary classification for the case of variable edge lengths (a^2b^2c, a^3bc, a^3b^2) together with he assumption that there is a tile such that all vertices have degree 3. I showed that there is no tiling with edge length combinations a^2b^2c and a^3bc, and there are several “tilings” for the edge length combinations a^3b^2. Much progress has been made since 4 years ago. It turns out that the earlier examples are fake after we take into account of spherical trigonometry. We have established a comprehensive framework for the project. First we have some “statistical results” regarding the distribution of degrees of vertices, special tiles, and angles. We also established some very useful and important constraints from spherical geometry (that the earlier examples fail to satisfy). Then we divided our projects into three cases according to the edge length combination of the pentagon: (1) Variable edge length: a^2b^2c, a^3bc, a^3b^2. (2) Equilateral: a^5. (3) Almost equilateral: a^4b. The first case is almost complete, where we expect the only tilings are what we call pentagonal subdivisions and double pentagonal subdivisions. The second case is opposite to the first, in that no edge length information can be used. The case is solved by a completely different method. We found there are exact 8 tilings of sphere by congruent pentagons. The third case is the most complicated. We already found some interesting families of tilings in some simple subcases of the third case.

 

Vertex and edge transitive graphs over doubled cycles  submitted by  Aleksander Malnic
Bostjan Kuzman, Aleksander Malnic, Primoz Potocnik

In order to complete (and generalize) a result of Gardiner and Praeger on 4-valent symmetric graphs (European J. Combin, 15 (1994), 375--381) we apply the lifting method in the context of elementary-abelian covering projections. In particular, for $p \ne 2$, the graphs whose quotient by some $p$-elementary abelian group of automorphisms is a cycle are described in terms of cyclic codes.

 

Vertex-primitive $s$-arc-transitive digraphs  submitted by  Binzhou Xia
Michael Giudici, Cai Heng Li and Binzhou Xia

An $s$-arc in a digraph (directed graph) is a sequence $v_0,v_1,\dots,v_s$ of vertices such that for each admissible $i$, the pair $(v_i,v_{i+1})$ is an arc of the digraph. A digraph $\Gamma$ is said to be $s$-arc-transitive if the automorphism group $\mathrm{Aut}(\Gamma)$ of $\Gamma$ acts transitively on the set of $s$-arcs of $\Gamma$, and is said to be vertex-primitive if $\mathrm{Aut}(\Gamma)$ is transitive and preserves no nontrivial partition of the vertex set. In this talk I will determine the O'Nan-Scott types of vertex-primitive groups that are possible for a $s$-arc-transitive digraph and discuss the maximal possible $s$.

 

Vertex-transitive graphs with large automorphism groups  submitted by  Robert Jajcay
Robert Jajcay

A conjecture about vertex-transitive graphs predicts that almost all vertex-transitive graphs are Cayley graphs with trivial vertex-stabilizers. On the other hand, when it comes to classification, vertex-transitive graphs possessing large vertex-stabilizer groups are usually the hardest cases to consider. In view of these observations, a parameter introduced to measure the distance of a vertex-transitive graph from being Cayley called {\em Cayley deficiency} is of particular interest with regard to the above conjecture as well as with regard to the classification of vertex-transitive graphs. The Cayley deficiency of a vertex-transitive graph $\Gamma$ is the order of a smallest vertex-stabilizer in a vertex-transitive group of automorphisms of $\Gamma$, or equivalently, it is the ratio of a smallest vertex-transitive automorphism group of $\Gamma$ and the order of $\Gamma$. Thus, a vertex-transitive graph is Cayley if and only if its Cayley deficiency is equal to $1$, and is non-Cayley if and only if its Cayley deficiency is at least $2$ (with the Cayley deficiency of the Petersen graph equal to $2$). We use the example of Johnson graphs to show that the Cayley deficiency can be arbitrarily large. Furthermore, a vertex-transitive graph is said to be quasi-Cayley if it admits a family of automorphisms acting regularly on its vertices, i.e., having the property that for every pair of of vertices of the graph there is exactly one member of the family mapping the first vertex onto the second. Based on the concept of a quasi-Cayley graph, the {\em quasi-Cayley index} of a vertex-transitive graph is defined to be the ratio between the order of a smallest $r$-regular family of automorphisms of the graph and its order (an $r$-regular family contains $r$ automorphisms mapping any given vertex to any other given vertex). We us the Johnson graphs again to show that the quasi-Cayley index can be arbitrarily large as well and use the Praeger-Xu graphs to show that the difference between the quasi-Cayley and Cayley indices can be arbitrarily large. The results described in this lecture come from joint work with Gareth Jones, Primoz Potocnik and Steve Wilson.

 

Vertex-transitive-odd numbers  submitted by  Klavdija Kutnar
Klavdija Kutnar, Ademir Hujdurovič, and Dragan Marušič

Following [{\em Ars Math. Contemp.} {\bf 10} (2016), 427--437], an automorphism of a graph is said to be {\em even/odd} if it acts on the vertex set of the graph as an even/odd permutation. A positive integer $n$ is said to be a {\em vertex-transitive-odd number} (in short, a {\em VTO-number}) if every vertex-transitive graph of order $n$ admits an odd automorphism. In this talk I will present recent results on this topic: There exists infinitely many VTO numbers which are square-free and have arbitrarily long prime factorizations. Cayley numbers congruent to $2$ modulo $4$, cubefree nilpotent Cayley numbers congruent to $3$ modulo $4$, and numbers of the form $2p$, $p$ a prime, are VTO numbers. At the other extreme, for a positive integer $n$ the complete graph $K_n$ and its complement are the only vertex-transitive graphs of order $n$ admitting odd automorphisms if and only if $n$ is a Fermat prime. This is a joint work with Ademir Hujdurovi\'c and Dragan Maru\v si\v c.