Cycle lengths in randomly perturbed graphs

Elad Aigner-Horev, Dan Hefetz, Michael Krivelevich

    פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

    2 ציטוטים ‏(Scopus)

    תקציר

    Let (Figure presented.) be an (Figure presented.) -vertex graph, where (Figure presented.) for some (Figure presented.). A result of Bohman, Frieze and Martin from 2003 asserts that if (Figure presented.), then perturbing (Figure presented.) via the addition of (Figure presented.) random edges, a.a.s. yields a Hamiltonian graph. We prove several improvements and extensions of the aforementioned result. In particular, keeping the bound on (Figure presented.) as above and allowing for (Figure presented.), we determine the correct order of magnitude of the number of random edges whose addition to (Figure presented.) a.a.s. yields a pancyclic graph. Moreover, we prove similar results for sparser graphs, and assuming the correctness of Chvátal's toughness conjecture, we handle graphs having larger independent sets. Finally, under milder conditions, we determine the correct order of magnitude of the number of random edges whose addition to (Figure presented.) a.a.s. yields a graph containing an almost spanning cycle.

    שפה מקוריתאנגלית
    עמודים (מ-עד)867-884
    מספר עמודים18
    כתב עתRandom Structures and Algorithms
    כרך63
    מספר גיליון4
    מזהי עצם דיגיטלי (DOIs)
    סטטוס פרסוםפורסם - דצמ׳ 2023

    טביעת אצבע

    להלן מוצגים תחומי המחקר של הפרסום 'Cycle lengths in randomly perturbed graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

    פורמט ציטוט ביבליוגרפי