A conjecture of Norine and Thomas for abelian Cayley graphs

MaRDI QIDQ2409829zbMATH OpenFDO

Authors Fuliang Lu, Lianzhu Zhang

Publication date 16 October 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p65

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

abelian groupsCayley graphsperfect matchingsPfaffian graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Review text

Summary: A graph \(\Gamma_1\) is a matching minor of \(\Gamma\) if some even subdivision of \(\Gamma_1\) is isomorphic to a subgraph \(\Gamma_2\) of \(\Gamma\), and by deleting the vertices of \(\Gamma_2\) from \(\Gamma\) the left subgraph has a perfect matching. Motivated by the study of Pfaffian graphs (the numbers of perfect matchings of these graphs can be computed in polynomial time), we characterized abelian Cayley graphs which do not contain a \(K_{3,3}\) matching minor. Furthermore, the Pfaffian property of Cayley graphs on abelian groups is completely characterized. This result confirms that the conjecture posed by \textit{S. Norine} and \textit{R. Thomas} [J. Comb. Theory, Ser. B 98, No. 5, 1038--1055 (2008; Zbl 1171.05040)] for abelian Cayley graphs is true.

Recommendations

• The Pfaffian property of Cayley graphs on dihedral groups
• Minimally non-Pfaffian graphs
• A note on the matching preclusion number of Caylay graphs on abelian groups with given degree
• Matching signatures and Pfaffian graphs
• Drawing 4-Pfaffian graphs on the torus

Cites work

• A characterisation of Pfaffian near bipartite graphs
• A characterization of convertible (0,1)-matrices
• A generalization of Little's theorem on Pfaffian orientations
• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• Enumeration of perfect matchings of a type of Cartesian products of graphs
• Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
• Hamiltonian decompositions of Cayley graphs on Abelian groups
• Hamiltonian decompositions of Cayley graphs on abelian groups of even order
• scientific article; zbMATH DE number 13859 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Matching theory
• Minimally non-Pfaffian graphs
• On 1-factorizability of Cayley graphs
• Permanents, Pfaffian orientations, and even directed circuits
• Pfaffian graphs embedding on the torus
• Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
• Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups
• Pólya's permanent problem
• The Pfaffian property of Cartesian products of graphs
• The Pfaffian property of circulant graphs
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface

Cited in

(2)

• The Pfaffian property of Cayley graphs on dihedral groups
• On the non-existence of Abelian Moore Cayley graphs with excess one

This page was built for publication: A conjecture of Norine and Thomas for abelian Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409829)