𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Matchings in Graphs on Non-orientable Surfaces

✍ Scribed by Glenn Tesler

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
345 KB
Volume
78
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We generalize Kasteleyn's method of enumerating the perfect matchings in a planar graph to graphs embedding on an arbitrary compact boundaryless 2-manifold S. Kasteleyn stated that perfect matchings in a graph embedding on a surface of genus g could be enumerated as a linear combination of 4 g Pfaffians of modified adjacency matrices of the graph. We give an explicit construction that not only does this, but also does it for graphs embedding on non-orientable surfaces. If a graph embeds on the connected sum of a genus g surface with a projective plane (respectively, Klein bottle), the number of perfect matchings can be computed as a linear combination of 2 2g+1 (respectively, 2 2g+2 ) Pfaffians. Thus for any S, this is 2 2&/(S ) Pfaffians. We also introduce crossing orientations,'' the analogue of Kasteleyn's admissible orientations'' in our context, describing how the Pfaffian of a signed adjacency matrix of a graph gives the sign of each perfect matching according to the number of edge-crossings in the matching. Finally, we count the perfect matchings of an m_n grid on a Mo bius strip.

πŸ“œ SIMILAR VOLUMES

Long cycles in 3-connected graphs in ori
Long cycles in 3-connected graphs in orientable surfaces
✍ Laura Sheppardson; Xingxing Yu πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 157 KB πŸ‘ 1 views

## Abstract In this article, we apply a cutting theorem of Thomassen to show that there is a function __f__: N β†’ N such that if __G__ is a 3‐connected graph on __n__ vertices which can be embedded in the orientable surface of genus __g__ with face‐width at least __f__(__g__), then __G__ contains a

On the Connectivity of Graphs Embedded i
On the Connectivity of Graphs Embedded in Surfaces
✍ Michael D Plummer; Xiaoya Zha πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 376 KB

In a 1973 paper, Cooke obtained an upper bound on the possible connectivity of a graph embedded in a surface (orientable or nonorientable) of fixed genus. Furthermore, he claimed that for each orientable genus #>0 (respectively, nonorientable genus #Γ„ >0, #Γ„ {2) there is a complete graph of orientab

A note on defective colorings of graphs
A note on defective colorings of graphs in surfaces
✍ Dan Archdeacon πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 139 KB πŸ‘ 2 views

A graph is (rn, k)-colorable if its vertices can be colored with rn colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. In a recent paper Cowen. Cowen, and Woodall proved that, for each compact surface S, there exists an integer k = k(S) such that eve

Long Cycles in Graphs on a Fixed Surface
Long Cycles in Graphs on a Fixed Surface
✍ Thomas BΓΆhme; Bojan Mohar; Carsten Thomassen πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 117 KB

We prove that there exists a function a: N 0 Γ— R + Q N such that (i) If G is a 4-connected graph of order n embedded on a surface of Euler genus g such that the face-width of G is at least a(g, e), then G can be covered by two cycles each of which has length at least (1 -e) n. We apply this to deri