๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Enumeration of Perfect Matchings in Graphs with Reflective Symmetry

โœ Scribed by Mihai Ciucu

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
759 KB
Volume
77
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

โœฆ Synopsis

A plane graph is called symmetric if it is invariant under the reflection across some straight line. We prove a result that expresses the number of perfect matchings of a large class of symmetric graphs in terms of the product of the number of matchings of two subgraphs. When the graph is also centrally symmetric, the two subgraphs are isomorphic and we obtain a counterpart of Jockusch's squarishness theorem. As applications of our result, we enumerate the perfect matchings of several families of graphs and we obtain new solutions for the enumeration of two of the ten symmetry classes of plane partitions (namely, transposed complementary and cyclically symmetric, transposed complementary) contained in a given box. Finally, we consider symmetry classes of perfect matchings of the Aztec diamond graph and we solve the previously open problem of enumerating the matchings that are invariant under a rotation by 90 degrees.

๐Ÿ“œ SIMILAR VOLUMES

Special parity of perfect matchings in b
Special parity of perfect matchings in bipartite graphs
โœ Ron Aharoni; Rachel Manber; Bronislaw Wajnryb ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 527 KB

Let G be a bipartite graph in which every edge belongs to some perfect matching, and let D be a subset of its edge set. It is shown that M fl D has the same parity for every perfect matching M if and only if D is a cut, and equivalently if and only. if (G, D) is a balanced signed-graph. This gives n

Maximal matchings in graphs with large n
Maximal matchings in graphs with large neighborhoods of independent vertices
โœ I. Rinsma; C. H. C. Little; D. R. Woodall ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| โ‰ฅ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.

Factorization of interaction graphs with
Factorization of interaction graphs with n-fold symmetry: Some applications in PPP calculation and molecular vibrational analysis
โœ Jayanta Sarkar; Asok K. Mukherjee ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 506 KB

The (6 and iF matrices in the molecular vibration problem, the secular matrix in Hiickel calculation including some nonneighbor interactions, and the Fock matrices at any stage of iteration in the Parker-Parr-Pople (PPP) calculations on cis-and trans-butadiene, benzene, and s-triaminobenzene systems