Small maximal matchings of random cubic graphs

H. Assiyatun*, W. Duckworth

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We consider the expected size of a smallest maximalmatching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs.We analyze the averagecase performance of this heuristic on random n-vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximalmatching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n-vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n-vertex cubic graph is a.a.s. larger than 0.3158n.

    Original languageEnglish
    Pages (from-to)293-323
    Number of pages31
    JournalJournal of Graph Theory
    Volume62
    Issue number4
    DOIs
    Publication statusPublished - Dec 2009

    Fingerprint

    Dive into the research topics of 'Small maximal matchings of random cubic graphs'. Together they form a unique fingerprint.

    Cite this