The Pfaffian property of circulant graphs
The Pfaffian property of circulant graphs
复制标题
循环图的普法夫性质
DOI：
10.1016/j.dam.2014.09.002
复制
发表时间：
2015-01
影响因子：
1.1
通讯作者：
Yan Wang
中科院分区：
文献类型：
--
作者：
Fuliang Lu;Lianzhu Zhang;Yan Wang
The importance of the Pfaffian property of a graph stems from the fact that if the graph is Pfaffian, then the number of its perfect matchings can be computed in polynomial time. A graph G is Pfaffian if there exists an orientation of G, denoted by G ⃗, such that the determinant of the skew adjacency matrix of G ⃗ equals the square of the number of perfect matchings of G. An undirected graph G=(V, E) with n vertices is a circulant graph, denoted by C n (a 1, a 2,…, a m), if there exists a labeling of the vertices of G, v 1, v 2,…, v n, and m integers, a 1, a 2,…, a m, such that the edge set E={v i v j: i− j≡±a k (mod n) for 1≤ k≤ m}. In this paper, the Pfaffian property of circulant graphs is completely characterized, that is, a simple connected circulant graph C n (a 1, a 2,…, a m) of even order is Pfaffian if and only if m= 1 or, m= 2 and a 1+ a 2 is odd.
登录
查看更多内容
DOI：
10.1016/j.jctb.2007.12.005
发表时间：
2008-09
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Sergey Norin;R. Thomas
通讯作者：
Sergey Norin;R. Thomas
DOI：
10.1016/s0196-8858(03)00097-6
发表时间：
2004-05
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
Weigen Yan;Fuji Zhang
通讯作者：
Weigen Yan;Fuji Zhang
DOI：
10.1016/s0021-9800(70)80068-0
发表时间：
1970-10
期刊：
Journal of Combinatorial Theory, Series A
影响因子：
--
作者：
B. Elspas;James Turner
通讯作者：
B. Elspas;James Turner
DOI：
10.1016/0095-8956(75)90048-9
发表时间：
1975-06
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
C. Little
通讯作者：
C. Little
DOI：
10.1090/s0002-9947-1991-1040045-3
发表时间：
1991-02
影响因子：
1.3
作者：
C. Thomassen
通讯作者：
C. Thomassen