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

Let G be a graph. It is known that Aut(G) x Z(2) is contained in Aut(G x K-2) where G x K-2 is the direct product of G with K-2. When this inclusion is strict, the graph G is called unstable. We define the index of instability of G asvertical bar Aut(G x K-2)vertical bar/2 vertical bar Aut(G)vertical barIn 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. (C) 2018 Elsevier B.V. All rights reserved.