Infinite families of asymmetric graphs. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Brewer, Alejandra; Gregory, Adam; Jones, Quindel; Rodriguez, Luke; Flórez, Rigoberto; Narayan, Darren
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 1000
• Page End: 1009
• Publication Date: 2020-09-01
• Subjects: Graph automorphisms -- asymmetric graphs -- Hamiltonian graphs
• DOI: 10.1016/j.akcej.2019.08.011
• Languages: English
• ISSNs: 0972-8600

Abstract

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 q ( n − 1 ) − ⌊ n − 1 2 ⌋, 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 4 ≤ n ≤ 10 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 k ≥ 3 .