科研之友
微信
新浪微博
Facebook
分享链接
摘要
A graph with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results.
- 出版日期2018-4
- 单位厦门大学
