Abstract
A catacondensed polyhex \(H\) is a connected subgraph of a hexagonal system such that any edge of \(H\) lies in a hexagon of \(H\), any triple of hexagons of \(H\) has an empty intersection and the inner dual of \(H\) is a cactus graph. A perfect matching \(M\) of a catacondensed polyhex \(H\) is relevant if every cycle of the inner dual of \(H\) admits a vertex that corresponds to the hexagon which contributes three edges in \(M\). The vertex set of the graph \(\tilde R(H)\) consists of all relevant perfect matchings of \(H\), two perfect matchings being adjacent whenever their symmetric difference forms the edge set of a hexagon of \(H\). A labeling that assigns in linear time a binary string to every relevant perfect matching of a catacondensed polyhex is presented. The introduced labeling defines an isometric embedding of \(\tilde R(H)\) into a hypercube.
