Realizing the asymmetric index of a graph (Q6586642)

If an automorphism group of a graph is trivial then we call it asymmetric. \textit{P. Erdős} and \textit{A. Rényi} [Acta Math. Acad. Sci. Hung. 14, 295--315 (1963; Zbl 0118.18901)] probed the problem of removing some \(r\) number of edges and adding some \(s\) number of edges so that the resulting graph is non-asymmetric. The minimum of \(r+s\) so that the resulting graph is asymmetric is called the asymmetric index \(\operatorname{ai}(G)\) of \(G\). The authors of this paper probe \(\operatorname{ai}(G)\) for both connected and disconnected graphs including paths, cycles, and grids, with the addition of up to two isolated vertices. They found the number of labelled asymmetric graphs that can be obtained by adding or removing \(\operatorname{ai}(G)\) edges. A graph \(G\) is called minimally non-asymmetric if the probability \(P\{G: \operatorname{ai}(G) = 1\} =1\). Here, they construct infinite families of minimally non-asymmetric graphs.