On the asymmetry of random regular graphs and random graphs

descriptionPublicationkeyboard_double_arrow_right Article 19 Sep 2002 English Publisher:WileyJournal:Random Structures & Algorithms, volume 21, pages 216-224 (issn: 1042-9832, eissn: 1098-2418,

Copyright policy )

Authors: Jeong Han Kim; Benny Sudakov; Van H. Vu;

doi: 10.1002/rsa.10054

On the asymmetry of random regular graphs and random graphs

- Summary
- Subjects
- Metrics

Abstract

AbstractThis 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, 2002

Related Organizations

Microsoft (United States)
United States
University of California, San Diego
United States
Institute for Advanced Study
United States
College of New Jersey
United States

Keywords

Random graphs (graph-theoretic aspects)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	46
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average