Infinite families of asymmetric graphs

Abstract

A graph G is asymmetric if its automorphism group of vertices is trivial. Asymmetric graphs were introduced by Erdős and Rényi in 1963. They showed that the probability of a graph on n vertices being asymmetric tends to 1 as n tends to infinity. In this paper, we first consider the enumeration of asymmetric trees, a question posed by Erdős and Rényi. We show that the number of asymmetric subdivided stars is approximately where q(n) is the number of ways to sum to n using distinct positive integers found by Hardy and Ramanujan in 1918. We also investigate cubic Hamiltonian graphs where asymmetry, where at least for small values of n, seem to be rare. It is known that none of the cubic Hamiltonian graphs on vertices are asymmetric, and of the 80 cubic Hamiltonian graphs on 12 vertices only 5 are asymmetric. We give a construction of an infinite family of cubic Hamiltonian graphs that are asymmetric. Then we present an infinite family of quartic Hamiltonian graphs that are asymmetric. We use both of the above results for cubic and quartic asymmetric Hamiltonian graphs to establish the existence of k-regular asymmetric Hamiltonian graphs for all

Keywords

• graph automorphisms
• asymmetric graphs
• hamiltonian graphs