The Pfaffian property of Cayley graphs on dihedral groups (Q2197482): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2020.07.006 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3043737820 / rank | |||
Normal rank |
Revision as of 22:40, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Pfaffian property of Cayley graphs on dihedral groups |
scientific article |
Statements
The Pfaffian property of Cayley graphs on dihedral groups (English)
0 references
31 August 2020
0 references
If \(G\) is a group with identity element 1, and \(S\) is any subset of elements with \(1\notin S\) which is closed under the taking of inverses, the authors define the Cayley graph \(\Gamma(G,S)\) as the directed graph on vertex set \(G\), where an edge connects vertex \(x\) to vertex \(y\) iff \(x^{-1}y\in S\); caveat lector: the authors' definition does not require that \(S\) be a set of generators, or even that it be nonempty! For basic properties of Pfaffian orientations, the authors suggest [\textit{R. Thomas}, in: Proceedings of the international congress of mathematicians (ICM), Madrid, Spain, August 22--30, 2006. Volume III: Invited lectures. Zürich: European Mathematical Society (EMS). 963--984 (2006; Zbl 1101.05054)]; \(\mathbb{Z}_n(a_1,\dots,a_m),\left(a_1,\dots,a_m\in\left[0,\frac n2\right]\right)\) denotes the circulant graph with vertices \(v_1,v_2,\dots,v_n\) labelled with the integers modulo \(n\) and edge-set \(\{v_iv_j:i-j\equiv\pm a_k \pmod n,1\le k\le m\}\). \par In this paper, the authors characterize the Pfaffian property of Cayley graphs on dihedral groups: Theorem 14 states that if \(\Gamma(D_n,S)\) is a connected Cayley graph on a dihedral group \(D_n\) of order \(2n\), then \(\Gamma(D_n,S)\) is Pfaffian if and only if it is isomorphic to one of the following graphs ``or its spanning subgraph'' (sic): (1) the Cartesian product of \(\mathbb{Z}_{2n}(1,2n-1,n)\) and a path of length 2, where \(n\) is even; (2) the Heawood 6-cage; (3) the Cayley graph \(\mathbb{Z}_{2n}(s,t)\), where \(s+t\) is odd; (4) the Cartesian product of the cycle graphs of orders \({\frac n2}\) and \(4\), where \(\frac n2\) is odd.
0 references
Pfaffian orientation
0 references
Cayley graph
0 references
dihedral group
0 references
perfect matching
0 references