A conjecture of Norine and Thomas for abelian Cayley graphs (Q2409829): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1625489 |
Changed an Item |
||
Property / author | |||
Property / author: Lian Zhu Zhang / rank | |||
Normal rank |
Revision as of 03:43, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A conjecture of Norine and Thomas for abelian Cayley graphs |
scientific article |
Statements
A conjecture of Norine and Thomas for abelian Cayley graphs (English)
0 references
16 October 2017
0 references
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.
0 references
perfect matchings
0 references
Pfaffian graphs
0 references
Cayley graphs
0 references
abelian groups
0 references