Người báo cáo: Ngô Việt Trung
Thời gian: 9h30, thứ 5, ngày 22/5/2014
Địa điểm: Phòng 201, nhà A5, Viện Toán học, 18 Hoàng Quốc Việt, Cầu Giấy, Hà Nội
Tóm tắt: A matching-critical graph is a simple graph G such that if we delete any node, the resulting graph contains a maximum matching of G. Inspired from a problem in Commutative Algebra we have to generalize this notion to weighted graphs. The problem here is to to characterize the base graphs (or the supports) of matching critical weighted graphs with a given matching number. It turns out that the base graph of a matching-critical weighted graph is a strongly non-bipartite graph. Such a graph always have ear decompositions which decompose each connected components into a sequence of paths such that the first path is a cycle and the endpoints of each other path are the only vertices belonging to earlier paths in the sequence. Our main result shows that the existence of a matching-critical weighted graph on a strongly non-bipartite graph depends solely on the optimal number of even ears in such ear decompositions. This result raises some interesting problems on matching numbers of weighted graphs. |
