𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Small maximal matchings of random cubic graphs

✍ Scribed by H. Assiyatun; W. Duckworth

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
330 KB
Volume
62
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623__n__. 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.3214__n__. 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.3158__n__. Β© 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009

πŸ“œ SIMILAR VOLUMES

Maximal matchings in graphs with large n
Maximal matchings in graphs with large neighborhoods of independent vertices
✍ I. Rinsma; C. H. C. Little; D. R. Woodall πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| β‰₯ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.

Random Matchings Which Induce Hamilton C
Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs
✍ Jeong Han Kim; Nicholas C. Wormald πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 215 KB

Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set

Nonexistence of certain cubic graphs wit
Nonexistence of certain cubic graphs with small diameters
✍ Leif K. JΓΈrgensen πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 560 KB

We consider the maximum number of vertices in a cubic graph with small diameter. We show that a cubic graph of diameter 4 has at most 40 vertices. (The Moore bound is 46 and graphs with 38 vertices are known.) We also consider bipartite cubic graphs of diameter 5, for which the Moore bound is 62. We