Graph theory for alternating hydrocarbons with attached ports

Properties of molecules of certain hydrocarbons give rise to difficult questions in graph theory. This paper is primarily devoted to the graph theory, but the physico-chemical motivation, which is somewhat speculative, is also presented. Molecules of unsaturated hydrocarbons exhibit alternating paths with single and double bonds. Such alternating paths have been postulated to be electrically conductive. When used to conduct, however, such a path is toggled: the single and double bonds are interchanged. This can imply that other alternating paths appear or disappear. In this way, switching behavior arises. This suggests a possibility of molecular computing. Molecules are represented by graphs where certain nodes, called ports, are chosen as connectors to the outside world. At these ports other chemical groups can be attached to observe and influence the behavior. A choice of single and double bonds in the molecule is represented by an almost-perfect matching in the graph—almost, in the sense that the ports and only the ports are allowed to have no double bond attached to them. The corresponding graph theory is a qualitative idealization of the molecules. It turns out that the switching behavior is completely determined by sets of ports, called cells. The paper is devoted to the question which cells are Kekule cells, i.e., correspond to almost-perfect matchings in graphs. We prove that every Kekule cell is what is known as a linkable Δ -matroid (it appears that this was known). An anonymous referee showed us the existence of a linkable Δ -matroid with 7 ports that is not a Kekule cell. The argument is presented. We classify the linkable cells with ≤ 5 ports and show that they all are Kekule cells. We also classify the linkable cells with 6 ports. There are 214 classes; 210 classes contain Kekule cells; only 4 classes are undecided.