tailieunhanh - Báo cáo toán học: "Maximum matchings in regular graphs of high girth"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Maximum matchings in regular graphs of high girth. | Maximum matchings in regular graphs of high girth Abraham D. Flaxman Microsoft Research Redmond Washington USA abie@ Shlomo Hoory IBM Research Laboratory Haifa Israel shlomoh@ Submitted April 22 2006 Accepted Dec 10 2006 Published Jan 3 2007 Mathematics Subject Classification 05C70 Abstract 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 b g 1 2j around a vertex for odd values of g and around an edge for even values of g. This result is tight if n 2n0 d g . 1 Introduction For a graph G a matching or one-factor of G is a subgraph of G in which each vertex has degree at most one. A basic question in combinatorial optimization is What is the size of a maximum matching in a given graph This has been explored extensively as an algorithmic question and a number of efficient procedures are known which find a maximum matching of a given graph. This note considers the question from a different angle. What general graph properties imply that a graph must contain a large matching This note shows that in regular graphs high girth is such a property. The notation used in this note is collected in this paragraph. For the graph G V E and u v 2 V write u v if and only if u vg 2 E and abbreviate u vg with uv when it is clear from context that this refers to an edge. For S c V write G S to denote the graph G induced by the vertices S and write E S to denote the edges in G S . The girth of a graph G is the length of the shortest cycle in G. When dealing with a different graph say H write V H to denote the vertex set of H and E H to denote the edge set. Finally say that G is a d g -graph if it is a d-regular graph of girth at least g. THE ELECTRONIC JOURNAL OF .