×

Perfect matchings in hexagonal systems. (English) Zbl 0542.05048

A hexagonal system (HS) is a finite connected plane graph with no cut- vertices in which every interior region is a hexagonal unit cell. The author provides a simple and fast algorithm for finding a perfect matching (PM) in an HS if it exists. He also characterizes the set of all PM’s in a given HS. The results do have applications in chemistry, since an HS with a PM represents a certain molecule.
Reviewer: Ch.Schulz

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B50 Polyominoes
05B40 Combinatorial aspects of packing and covering
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] F. Harary, The cell growth problem and its attempted solutions,Beiträge zur Graphentheorie (Int. Koll. Manebach, 9–12. Mai 1967), ed. H. Sachs, H.–J. Voss, and H. Walther. B. G. Teubner Verlagsgesellschaft Leipzig 1968, 49–60.
[2] J. E. Hopcroft andR. M. Karp, An 5/2 algorithm for maximum matchings in bipartite graphs,SIAM J. Comput. 2 (1973) 225–231. · Zbl 0266.05114 · doi:10.1137/0202019
[3] E. L. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976. · Zbl 0413.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.