The Pfaffian property of Cartesian products of graphs
The Pfaffian property of Cartesian products of graphs
复制标题
DOI：
10.1007/s10878-012-9533-4
复制
发表时间：
2014-04
影响因子：
1
通讯作者：
Fuliang Lu;Lian-zhu Zhang
中科院分区：
文献类型：
--
作者：
Fuliang Lu;Lian-zhu Zhang
Suppose thatG=(V,E) is a graph with even vertices. An even cycleCis a nice cycle ofGifG−V(C) has a perfect matching. An orientation ofGis a Pfaffian orientation if each nice cycleChas an odd number of edges directed in either direction of the cycle. LetPnandCndenote the path and the cycle onnvertices, respectively. In this paper, we characterize the Pfaffian property of Cartesian productsG×P2nandG×C2nfor any graphGin terms of forbidden subgraphs ofG. This extends the results in (Yan and Zhang in Discrete Appl Math 154:145–157, 2006).
