Extrema concerning asymmetric graphs

AbstractBy a graph we mean a finite undirected graph without loops and without multiple edges. The automorphism group of a graph consists of those permutations of the vertex set of the graph which preserve adjacency relations. A graph is called asymmetric if its automorphism group consists only of the identity automorphism. In this paper we study questions pertaining to the existence and structure of asymmetric graphs.Specifically, we establish the extreme values of p and q for which there exist asymmetric graphs having p vertices and q edges. These extremes are obrained for the following four classes of graphs: all graphs, connected graphs, graphs having no vertices of degree 2 (topological graphs), and connected topological graphs.An asymmetric graph K is said to have asymmetry equal to 1 if it is possible by either adjoining one edge to K or deleting one edge of K to obtain a graph which is not asymmetric. For the above-mentioned four classes of graphs we resolve the following problem: determine the least value G(p, 1) for which there exists a graph having asymmetry equal to 1, having p vertices, and having G(p, 1) edges. This problem stated for the class of all graphs was posed by P. Erdös and A. Rényi, Asymmetric Graphs Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315