Face-width of Pfaffian braces and polyhex graphs on surfaces

zbMATH Open1305.05196arXiv0908.1506MaRDI QIDQ490246FDOQ490246

Dong Ye, Heping Zhang

Publication date: 22 January 2015

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

Abstract: A graph $G$ is Pfaffian if it has an orientation such that each central cycle $C$ (i.e. $C$ is even and $G-V(C)$ has a perfect matching) has an odd number of edges directed in either direction of the cycle. The number of perfect matchings of Pfaffian graphs can be computed in polynomial time. In this paper, by applying the characterization of Pfaffian braces due to Robertson, Seymour and Thomas [Ann. Math. 150 (1999) 929-975], and independently McCuaig [Electorn. J. Combin. 11 (2004) #R79], we show that every embedding of a Pfaffian brace on a surface with positive genus has face-width at most 3. For a Pfaffian cubic brace, we obtain further structure properties which are useful in characterizing Pfaffian polyhex graphs. Combining with polyhex graphs with face-width 2, we show that a bipartite polyhex graph is Pfaffian if and only if it is isomorphic to the cube, the Heawood graph or $C_{k}imes{K}_2$ for even integers $kge6$, and all non-bipartite polyhex graphs are Pfaffian.

Full work available at URL: https://arxiv.org/abs/0908.1506

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

Recommendations

• Pfaffian graphs embedding on the torus
• On the theory of Pfaffian orientations. I: Perfect matchings and permanents
• Pfaffian polyominos on the Klein bottle
• A sufficient condition for Pfaffian graphs on the torus
• Pfaffian orientations for a type of bipartite graph

zbMATH Keywords

embeddingPfaffian orientationperfect matchingpolyhex graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Matching theory
• Pólya's permanent problem
• A characterization of convertible (0,1)-matrices
• Permanents, Pfaffian orientations, and even directed circuits
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• A survey of Pfaffian orientations of graphs
• Title not available (Why is that?)
• Graphs on surfaces
• Embeddings of graphs with no short noncontractible cycles
• 2-extendability of toroidal polyhexes and Klein-bottle polyhexes
• On n-extendable graphs
• \(k\)-resonance in toroidal polyhexes
• Title not available (Why is that?)
• Matching structure and the matching lattice
• Title not available (Why is that?)
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Uniqueness and faithfulness of embedding of toroidal graphs
• Construction and enumeration of regular maps on the torus
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface
• 2-extendability and \(k\)-resonance of non-bipartite Klein-bottle polyhexes
• \(k\)-resonant toroidal polyhexes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Drawing
• Pfaffian labelings and signs of edge colorings

Cited In (2)

• The Pfaffian property of Cayley graphs on dihedral groups
• Homeomorphically irreducible spanning trees in hexangulations of surfaces

This page was built for publication: Face-width of Pfaffian braces and polyhex graphs on surfaces

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