The Pfaffian property of Cartesian products of graphs

DOI10.1007/s10878-012-9533-4zbMath1322.90078MaRDI QIDQ2015792

Fuliang Lu, Lian Zhu Zhang

Publication date: 24 June 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9533-4

zbMATH Keywords

perfect matchings; Cartesian products of graphs; Pfaffian graphs

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

Related Items

The Pfaffian property of circulant graphs, A sufficient condition for Pfaffian graphs on the torus, An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs, The Pfaffian property of Cayley graphs on dihedral groups, A conjecture of Norine and Thomas for abelian Cayley graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimally non-Pfaffian graphs
• Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
• Matching theory
• Even circuits of prescribed clockwise parity
• A characterization of convertible (0,1)-matrices
• A characterisation of Pfaffian near bipartite graphs
• Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
• Permanents, Pfaffian orientations, and even directed circuits
• Enumeration of perfect matchings of a type of Cartesian products of graphs
• The statistics of dimers on a lattice