GRAPHICAL PROPERTIES OF POLYHEXES - PERFECT MATCHING VECTOR AND FORCING
Additional Document Info
From the viewpoint of graph theory and its applications, subgraphs of the tiling of the plane with unit squares have long been studied in statistical mechanics, In organic chemistry, a much more relevant case concerns subgraphs of the tiling with unit hexagons. Our purpose here is to take a mathematical view of such polyhex graphs G and study two novel concepts concerning perfect matchings M. First, the forcing number of M is the smallest number of edges of M which are not contained in any other perfect matching of G. Second, the perfect matching vector of M is written (n3, n2, n1, n0), where nk is the number of hexagons with exactly k edges in M. We establish some initial results involving these two concepts and pose some questions. 1991 J.C. Baltzer AG, Scientific Publishing Company.