Time: 9h30, Thursday 22 May 2014
Location: Room 201, Building A5, Vietnam Institute of Mathematics, 18 Hoang Quoc Viet, Ha Noi
Abstract: 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.