Seminar on Combinatorics

主講者: | 張蓮珠教授 (廈門大學) |

講題: | Pfaffian orientations and perfect matchings of graphs |

時間: | 2012-03-30 (Fri.) 14:00 - 15:30 |

地點: | 數學所 722 研討室 (台大院區) |

Abstract: | A subgraph $H$ of a graph $G$ is central if $G\setminus V(H)$ has a perfect matching. An even cycle $C$ in a directed graph $D$ is called oddly oriented if, for either choice of direction of traversal around $C$, the number of edges of $C$ directed in the direction of traversal is odd. An orientation $D$ of a graph $G$ with an even number of vertices is called Pfaffian if every central cycle $C$ of $G$ is oddly oriented in $D$. A graph $G$ 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 $G$ is Pfaffian, then the number of perfect matchings of $G$ 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. |

|| Close window || |