Carnegie Mellon University
Browse
file.pdf (377.77 kB)

On a sparse random graph with minimum degree three: Likely Pósa sets are large

Download (377.77 kB)
journal contribution
posted on 2013-01-13, 00:00 authored by Alan FriezeAlan Frieze, Boris Pittel

We consider the endpoint sets produced by Pósa rotations, when applied to a longest path in a random graph with cn edges, conditioned on having minimum degree at least three. We prove that, for c≥2.7, the Pósa sets are likely to be almost linear in n, implying that the number of missing edges, each allowing either to get a longer path or to form a Hamilton cycle, is almost quadratic in n.

History

Publisher Statement

copyright © by International Press of Boston

Date

2013-01-13

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC