Abstract
A (3,6)-fullerene is a connected cubic plane graph whose faces are only triangles and hexagons, with connectivity 2 or 3. This paper focuses on (3,6)-fullerenes with connectivity 3, which are tubes consisting of concentric hexagonal layers capped by adjacent triangles. The structure is determined by three parameters: radius ($r$), size ($s$), and torsion ($t$). We derive exact counting formulas for the number of perfect matchings (Kekulé structures) in these graphs, specifically for the case where $s=4$. Our results verify the exponential lower bound conjecture proposed by Esperet et al. for cubic bridgeless graphs.
Introduction
In mathematical chemistry, a perfect matching—or Kekulé structure—is a fundamental descriptor for predicting the stability and resonance energy of molecular graphs. For general graphs, counting perfect matchings is an #P-complete problem. While formulas exist for standard (5,6)-fullerenes, a systematic study of (3,6)-fullerenes with connectivity 3 was previously lacking. This research addresses this gap by providing closed-form exponential formulas for a specific class of these graphs and testing them against the conjecture that every cubic bridgeless graph with $p$ vertices has at least $2^{p/3656}$ perfect matchings.
Structural Classification and Decomposition
The connectivity-3 (3,6)-fullerene, denoted as $Q_{r,s,t}$, is defined by its radius $r$ (number of rings), size $s$ (spokes per layer), and torsion $t$. A key insight of this work is that despite the variety of parameters, these graphs can be categorized into fundamental isomorphic types based on their structural symmetry.
The authors employ a structural decomposition approach to handle the complexity of these graphs:
- Cutting the Graph: The fullerene is "cut" by removing the inner cap and adding pendant vertices to create simpler subgraphs ($L_n$).
- Recurrence Relations: By analyzing the relationship between perfect matchings in a graph with $n$ layers versus $n-1$ layers, a system of linear recurrence equations is derived.
- Characteristic Equations: These recurrences are solved using characteristic roots (e.g., $2 \pm \sqrt{2}$) to produce exact formulas.
Results and Quantitative Validation
The study successfully derives exact formulas for the number of perfect matchings $|M(G)|$ based on the vertex count $p$ for the case $s=4$:
- For $n$ odd, $t=0$: $|M(G)| = 1 + 2^{p/8} + 2^{p/16} + (3+2\sqrt{2})(2+\sqrt{2})^{p/8-2} + \frac{1}{2}(2-\sqrt{2})^{p/8}$
- For $n$ odd, $t=2$: $|M(G)| = 1 + 2^{p/8} - 2^{p/16} + (3+2\sqrt{2})(2+\sqrt{2})^{p/8-2} + \frac{1}{2}(2-\sqrt{2})^{p/8}$
- For $n$ even: $|M(G)| = 1 + 2^{p/8} + (3-2\sqrt{2})(2-\sqrt{2})^{p/8-2} + (10+7\sqrt{2})(2+\sqrt{2})^{p/8-3}$
These formulas were validated against small-scale examples. For instance, a fullerene with parameters $(2,4,0)$ has 13 perfect matchings, while $(4,4,0)$ has 89. Crucially, the growth rate is shown to be governed by powers of $(2 + \sqrt{2})$, confirming that the number of matchings far exceeds the $2^{p/3656}$ lower bound proposed by Esperet et al.
Conclusion
This work provides a rigorous mathematical foundation for counting Kekulé structures in (3,6)-fullerenes with connectivity 3. While the current formulas are limited to the size parameter $s=4$, the recursive methodology established here can be extended to larger circumference tubes ($s > 4$) and other fullerene-like cubic planar graphs. This contributes to the broader effort of verifying lower bound conjectures for perfect matchings in complex molecular architectures.
Summary updated