Maximum induced matchings of random cubic graphs
type: Item
instance of: scholarly article
title: Maximum induced matchings of random cubic graphs
zbMATH Open document ID: 1001.05093
DOI: 10.1016/S0377-0427(01)00457-5
author: Nicholas Wormald
author: W. Duckworth
author: Michele Zito
published in: Journal of Computational and Applied Mathematics
publication date: 2002-08-22T00:00:00Z
review text: An algorithm to find large induced matchings in cubic graphs is described. It is an algorithm that has been shown to return an induced matching of order at least \(3n/20 + O(1)\) for a cubic graph of order \(n\) and that there are infinitely many such graphs for which only this bound is achieved. The algorithm is applied to random cubic graphs, and it is shown that the order of the induced matching \(M\) returned almost surely satisfies \(.270413n \leq |M|\leq .282069n\). The lower bound in the expected size was proved by numerically solving differential equations, and the upper bound was verified using direct expectation arguments.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1787595
zbMATH Keywords: matchings
zbMATH Keywords: random graphs
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: Q3682518
cites work: Induced matchings
cites work: On the approximability of the maximum induced matching problem
cites work: Minimum independent dominating sets of random cubic graphs
cites work: Problems and results in combinatorial analysis and graph theory
cites work: Induced matchings in bipartite graphs
cites work: Irredundancy in circular arc graphs
cites work: New results on induced matchings
cites work: Maximum induced matchings in graphs
cites work: On induced matchings
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: Q4263664
cites work: Q4938890
cites work: Q4944970
full work available at URL: s0377-0427(01)00457-5
OpenAlex ID: W2088411760
Recommended article: Q2766812
Recommended article: Small maximal matchings of random cubic graphs
Recommended article: Combinatorial Geometry and Graph Theory
Recommended article: Q4405637
Recommended article: Induced matchings in cubic graphs
Recommended article: Maximum matchings in a class of random graphs
Recommended article: Large Induced Matchings in Random Graphs
Recommended article: Complete matchings in random subgraphs of the cube
Recommended article: Matchings in random spanning subgraphs of cubelike graphs
Recommended article: Maximum induced matchings in graphs
description: scientific article; zbMATH DE number 1787595