Carnegie Mellon University
Browse

Hamilton cycles in random graphs with a fixed degree sequence

Download (178.57 kB)
journal contribution
posted on 2010-03-01, 00:00 authored by Colin Cooper, Alan FriezeAlan Frieze, Michael Krivelevich

Let d = d1 ≤ d2 ≤ · · · ≤ dn be a non-decreasing sequence of n positive integers, whose sum is even. Let Gn,d denote the set of graphs with vertex set [n] = {1, 2,... ,n} in which the degree of vertex i is di . Let Gn,d be chosen uniformly at random from Gn,d. It will be apparent from Section 4.3 that the sequences we are considering will all be graphic. We give a condition on d under which we can show that whp Gn,d is Hamiltonian. This condition is satisfied by graphs with exponential tails as well those with power law tails.

History

Publisher Statement

Copyright © 2010 Society for Industrial and Applied Mathematics

Date

2010-03-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC