scientific article; zbMATH DE number 15371

MaRDI QIDQ3972015zbMATH OpenFDO

Authors Horst Sachs

Publication date 25 June 1992

zbMATH Keywords

lattice graphlattice networkperfect matchingspoint lattice

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

[For the entire collection see Zbl 0698.00017.] A matching of a graph \(G\) is a subset of the edge set of \(G\) whose elements have pairwise no common end vertices; it is called perfect, if it covers all vertices of \(G\). A point lattice (to distinguish from the lattice in algebra) is a doubly periodic set \(S\) (i.e. such that there exist non-collinear vectors \(a\), \(b\) such that \(S+a=S+b=S\)) in the plane with no accumulation points. A lattice network is a doubly-periodic two- connected locally finite undirected plane graph whose vertex set is a point lattice. A subgraph \(G\) of a lattice network \(N\) induced by the vertices lying on a circuit \(C\) and in the interior of \(C\) is called a lattice graph. The balanced lattice graph is defined. The number of perfect matchings of such a graph \(G\) is computed as the absolute value of a certain determinant of order \(s\), where \(s\) is the number of sources of \(G\) in a certain auxiliary orientation.

Recommendations

• Perfect matchings in the triangular lattice
• Perfect matchings on a type of lattices with toroidal boundary
• Enumeration of perfect matchings of lattice graphs by Pfaffians
• Perfect matchings of cellular graphs
• On the number of perfect matchings of line graphs

Cited in

(21)

• The 2-matching lattice of a graph
• How to calculate the number of perfect matchings in finite sections of certain infinite plane graphs
• Remark on the dimer problem
• Perfect matchings of polyomino graphs
• Expressions for the perfect matching numbers of cubic l m n lattices and their asymptotic values
• A distributive lattice on the set of perfect matchings of a plane bipartite graph
• The number of matchings of low order in hexagonal systems
• Enumeration of Wiener indices in random polygonal chains
• Perfect matchings in the triangular lattice
• On maximal resonance of polyomino graphs
• The number of Kekulé structures of polyominos on the torus
• On counting perfect matchings in general graphs
• Perfect matchings of generalized polyomino graphs
• Perfect matchings in random polyomino chain graphs
• Perfect Matchings of the Small Polyominoes
• A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs
• Matchings in Lattice Graphs and Hamming Graphs
• On \(k\)-resonance of grid graphs on the plane, torus and cylinder
• Algorithmic Applications in Management
• Counting matchings in graphs
• Direct sum of distributive lattices on the perfect matchings of a plane bipartite graph

This page was built for publication:

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