CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Symmetry in Graphs - Part I
Org: Joy Morris (University of Lethbridge)

DEBRA BOUTIN, Hamilton College
New Techniques in the Cost of 2-Distinguishing Hypercubes  [PDF]

The distinguishing number of a graph is the smallest number of colors necessary to color the vertices so that no nontrivial automorphism preserves the color classes. If a graph can be distinguished with two colors, the distinguishing cost is the smallest possible size of the smaller color class. This talk will cover techniques in the distinguishing cost of certain graph products, mostly hypercubes.

KAREN COLLINS, Wesleyan University
The distinguishing number of posets and lattices  [PDF]

This is joint work with Ann Trenk (Wellesley College). In this talk, we survey results about the distinguishing chromatic number and the distinguishing number of posets and lattices.

RICHARD HAMMACK, Virginia Commonwealth University
Edge-transitive direct products of graphs  [PDF]

Via a new technique, we characterize the conditions under which a direct product of graphs is edge-transitive, arc-transitive, half-transitive or semi-symmetric. This yields a new result in the case that the product is bipartite. As an application, we get a new method of constructing classes of half-transitive and semi-symmetric graphs.

BOHDAN KIVVA, University of Chicago
Minimal degree of the automorphism group of primitive coherent configurations  [PDF]

The minimal degree of a permutation group is the minimum number of points not fixed by non-identity elements. Lower bounds on this have structural consequences. In 2014 Babai proved that the automorphism group of a strongly regular graph with n vertices has linear minimal degree, with known exceptions. Strongly regular graphs correspond to primitive coherent configurations of rank 3. We extend Babai's result to rank 4. We also show that the result extends to non-geometric primitive distance-regular graphs of bounded diameter. The proofs combine structural and spectral methods. The results have consequences to primitive permutation groups previously known using CFSG.

FLORIAN LEHNER, University of Warwick
On symmetries of vertex and edge colourings of graphs  [PDF]

Call a vertex or edge colouring of a graph asymmetric, if no non-trivial automorphism preserves it. An asymmetric edge colouring of a graph is an asymmetric vertex colouring of its line graph, so intuitively finding asymmentric edge colourings should be easier. This intuition is supported by the fact that many results on asymmetric vertex colourings have edge colouring counterparts. Kalinowski and Pil{\'s}niak further showed that if a graph has an asymmetric vertex $k$-colouring, then it has an asymmetric edge $(k+1)$-colouring. We give a new proof of this result and fully characterise the graphs for which the bound is sharp.