On the asymmetry of random regular graphs and random graphs
- 19 September 2002
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 21 (3-4) , 216-224
Abstract
This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 ≤ d ≤ n − 4 the random d‐regular graph on n vertices almost surely has no nontrivial automorphisms. This answers an open question of N. Wormald [13]. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 216–224, 2002Keywords
This publication has 11 references indexed in Scilit:
- Random regular graphs of high degreeRandom Structures & Algorithms, 2001
- The Probabilistic Method2000
- Models of Random Regular Graphs1999
- Nearly perfect matchings in regular simple hypergraphsIsrael Journal of Mathematics, 1997
- Uniform generation of random regular graphs of moderate degreeJournal of Algorithms, 1990
- The automorphism group of random graphs with a given number of edgesMathematical Proceedings of the Cambridge Philosophical Society, 1988
- Automorphisms of random graphs with specified verticesCombinatorica, 1984
- Large Regular Factors in Random Graphs1984
- The Asymptotic Number of Unlabelled Regular GraphsJournal of the London Mathematical Society, 1982
- Asymmetric graphsActa Mathematica Hungarica, 1963