Speaker : Professor Lianzhu Zhang(Xiamen University)
Title : Pfaffian orientations and perfect matchings of graphs
Time : 2012-03-30 (Fri) 14:00 - 15:30
Place : Seminar Room 722, Institute of Mathematics (NTU Campus)
Abstract: A subgraph of a graph is central if has a perfect matching. An even cycle in a directed graph is called oddly oriented if, for either choice of direction of traversal around , the number of edges of directed in the direction of traversal is odd. An orientation of a graph with an even number of vertices is called Pfaffian if every central cycle of is oddly oriented in . A graph with an even number of vertices is said to be Pfaffian if it admits a Pfaffian orientation. The significance of this notion stems from the fact that if a graph is Pfaffian, then the number of perfect matchings of can be computed in polynomial time. This was discovered by Kasteleyn and Fisher and has received considerable attention since then. In this talk, we address the question of characterizing Pfaffian graphs and enumeration of their perfect matchings.