Realizing the Asymmetric Index of a Graph

A graph G is asymmetric if its automorphism group is trivial. Asymmetric graphs were introduced by Erd\H{o}s and R\'{e}nyi Erdos [1]. They suggested the problem of starting with an asymmetric graph and removing some number, r , of edges and/or adding some number, s , of edges so that the resulting graph is non-asymmetric. Erd\H{o}s and R\'{e}nyi defined the degree of asymmetry of a graph to be the minimum value of r + s . In this paper, we consider another property that measures how close a given non-asymmetric graph is to being asymmetric. Brewer et al. defined the asymmetric index of a graph G , denoted a i ( G ) , as the minimum of r + s so that the resulting graph G is asymmetric [2]. It is noted that a i ( G ) is only defined for graphs with at least six vertices. We investigate the asymmetric index of both connected and disconnected graphs including paths, cycles, and grids, with the addition of up to two isolated vertices. Furthermore, for a graph in these families G , we determine the number of labeled asymmetric graphs that can be obtained by adding or removing a i ( G ) edges. This leads to the related question: Given a graph G where a i ( G ) = 1 , what is the probability that for a randomly chosen edge e , that G – e will be asymmetric? A graph is called minimally non-asymmetric if this probability is 1 . We give a construction of infinite families of minimally non-asymmetric graphs.