Minimally Non-Asymmetric Graphs and Balanced Incomplete Block Designs

Abstract

A graph is asymmetric if the automorphism group of its set of vertices is trivial. A graph is called non-asymmetric if and only if it is not asymmetric. A graph $G$ is minimally non-asymmetric if $G$ is non-asymmetric but $G–e$ is asymmetric for any edge $e$ contained in $G$.

Given a finite set $V$ (of elements called varieties) and integers $k$, $r$, and $\lambda$, a balanced incomplete block design (BIBD) is a family of $k$-element subsets of $V$, called blocks, such that any element is contained in $r$ blocks and any pair of distinct varieties $u$ and $w$ is contained in exactly $\lambda$ blocks.

In this paper, we give examples of minimally non-asymmetric graphs constructed from balanced incomplete block designs.