David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
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).
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998