Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
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).
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Charles A Micchelli
Journal of Approximation Theory