The construction of a smallest unstable asymmetric graph and a family of unstable asymmetric graphs with an arbitrarily high index of instability

Abstract

Let G be a graph. It is known that Aut(G) × Z2 is contained in Aut(G × K2) where G × K2 is the direct product of G with K2. When this inclusion is strict, the graph G is called unstable. We define the index of instability of G as

|Aut(G × K2)|

2|Aut(G)|

In his paper (Wilson, 2008, p. 370),Wilson gave an example which at the time was known as a smallest asymmetric unstable graph. In this paper, we construct an even smaller unstable asymmetric graph (on twelve vertices), and show that it is a smallest unstable asymmetric (that is, with trivial automorphism group) graph. We then extend this method to build a family of unstable asymmetric graphs with an arbitrarily large index of instability.