Infinite families of asymmetric graphs
Infinite families of asymmetric graphs
复制标题
无限个非对称图族
DOI：
10.1016/j.akcej.2019.08.011
复制
发表时间：
2020
影响因子：
1
通讯作者：
Narayan, Darren
中科院分区：
文献类型：
--
作者：
Brewer, Alejandra;Gregory, Adam;Jones, Quindel;Rodriguez, Luke;Flórez, Rigoberto;Narayan, Darren
一个图G是非对称的，如果它的顶点自同构群是平凡的。不对称图是由Erdens和Rényi在1963年提出的。他们证明了n个顶点的图不对称的概率趋于1，并且趋于无穷大。在本文中，我们首先考虑非对称树的计数，这是Erdens和Rényi提出的一个问题。我们证明了不对称的星的数目近似为其中q（n）是哈代和拉马努金在1918年发现的不同正整数求和的方法的数目。我们还研究了三次哈密顿图的不对称性，其中至少对于小值的n，似乎是罕见的。已知顶点上的三次Hamilton图中没有一个是不对称的，而在80个顶点上的三次Hamilton图中，只有5个是不对称的。本文给出了一类非对称的三次Hamilton图的构造.然后，我们提出了一个无限的家庭四次哈密顿图是不对称的。我们利用上面关于三次和四次非对称Hamilton图的两个结果来建立k-正则非对称Hamilton图的存在性，
A graphGisasymmetricif 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 onnvertices being asymmetric tends to 1 asntends 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 approximatelywhereq(n) is the number of ways to sum tonusing distinct positive integers found by Hardy and Ramanujan in 1918. We also investigate cubic Hamiltonian graphs where asymmetry, where at least for small values ofn, seem to be rare. It is known that none of the cubic Hamiltonian graphs onvertices 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 ofk-regular asymmetric Hamiltonian graphs for all