Enumeration of Highly Irregular Trees by Automorphism Group

Abstract

A connected graph is highly irregular if the neighbors of each vertex have distinct degrees. We will show that every highly irregular tree has at most one nontrivial automorphism. The question that motivated this work concerns the proportion of highly irregular trees that are asymmetric, i.e., have no nontrivial automorphisms. A $d$-tree is a tree in which every vertex has degree at most $d$. A technique for enumerating unlabeled highly irregular $d$-trees by automorphism group will be described for $d\ge 4$ and results will be given for $d=4$. It will be shown that, for fixed $d$, $d\ge 4$, almost all highly irregular $d$-trees are asymmetric.