EMBEDDINGS OF PFAFFIAN BRACES AND POLYHEX GRAPHS
Dong Ye, Heping Zhang · arXiv (Cornell University) · 2009
Let G be a graph admitting a perfect matching. A cycle of even size C is central if G − C has a perfect matching. Given an orientation to G, an even cycle C is oddly oriented if along either direction of traversal around C, the number of edges of C with the direction as the same as the traversal direction is odd. An orientation of G is Pfaffian if every central cycle of G is oddly oriented. A graph G is Pfaffian if it has a Pfaffian orientation. In this paper, we show that every embedding of a Pfaffian brace on a surface with positive genus has face-width at most three and that the cyclic edge-connectivity of a Pfaffian cubic brace different from the Heawood graph is four. Finally, we characterize all Pfaffian polyhex graphs.