Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Let G = (V, E) be any d-regular graph with girth g on n vertices, for d ≥ 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/n0(d, g), where n0(d, g) is the number of vertices in a ball of radius [(g - 1)/2] 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).
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
M. Tismenetsky
International Journal of Computer Mathematics