Premium
How many random edges make a dense graph hamiltonian?
Author(s) -
Bohman Tom,
Frieze Alan,
Martin Ryan
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10070
Subject(s) - struct , random graph , random regular graph , combinatorics , mathematics , graph , discrete mathematics , hamiltonian (control theory) , complement graph , line graph , voltage graph , computer science , pathwidth , mathematical optimization , programming language
This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding Θ(n) random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 33–42, 2003