Maximum matchings in regular graphs of high girth
type: Item
instance of: scholarly article
title: Maximum matchings in regular graphs of high girth
zbMATH Open document ID: 1111.05080
author: Abraham D. Flaxman
author: Shlomo Hoory
published in: The Electronic Journal of Combinatorics
publication date: 2007-03-12T00:00:00Z
full work available at URL: https://eudml.org/doc/127271
full work available at URL: v14i1n1.html
review text: Summary: Let \(G=(V,E)\) be any \(d\)-regular graph with girth \(g\) on \(n\) vertices, for \(d\geq 3\). This note shows that \(G\) has a maximum matching which includes all but an exponentially small fraction of the vertices, \(O((d-1)^{-g/2})\). Specifically, in a maximum matching of \(G\), the number of unmatched vertices is at most \(n/n_0(d,g)\), where \(n_0(d,g)\) is the number of vertices in a ball of radius \(\lfloor (g-1)/2\rfloor\) around a vertex, for odd values of \(g\), and around an edge, for even values of \(g\). This result is tight if \(n < 2n_0(d,g)\).
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 5132859
MaRDI profile type: Publication
Recommended article: Maximum matchings in regular graphs
Recommended article: Maximum matching in regular and almost regular graphs
Recommended article: On maximum matchings in almost regular graphs
Recommended article: Maximum matchings in a regular graph of specified connectivity and bounded order
Recommended article: On maximal matchings of connected graphs
Recommended article: Matchings in graphs of odd regularity and girth
Recommended article: Tight lower bounds on the size of a maximum matching in a regular graph
Recommended article: A note on a conjecture on maximum matching in almost regular graphs
Recommended article: Maximum matchings in a class of random graphs
Recommended article: Q4825844
description: scientific article; zbMATH DE number 5132859