Skip navigation
Skip navigation

Small Maximal Matchings of Random Cubic Graphs

Assiyatun, Hilda; Duckworth, William


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...[Show more]

CollectionsANU Research Publications
Date published: 2009
Type: Journal article
Source: Journal of Graph Theory
DOI: 10.1002/jgt.20434


There are no files associated with this item.

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator