The Number of Perfect Matchings in (3,6)-Fullerene

Rui Yang, Mingzhu YuanWuhan 2023 · DOI

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.

Figure 6: Structural representations of different (3,6)-fullerene graph types $Q_n^1, Q_n^2, Q_n^3,$ and $Q_n^4$.

The authors employ a structural decomposition approach to handle the complexity of these graphs:

  1. Cutting the Graph: The fullerene is "cut" by removing the inner cap and adding pendant vertices to create simpler subgraphs ($L_n$).
  2. 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.
  3. 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

Abstract

A [see formula in PDF]-fullerene is a connected cubic plane graph whose faces are only triangles and hexagons, and has the connectivity [see formula in PDF] or [see formula in PDF]. The [see formula in PDF]-fullerenes with connectivity [see formula in PDF] are the tubes consisting of [see formula in PDF] concentric hexagonal layers such that each layer consists of two hexagons, capped on each end by two adjacent triangles, denoted by [see formula in PDF]. A [see formula in PDF]-fullerene [see formula in PDF] with [see formula in PDF] vertices has exactly [see formula in PDF] perfect matchings. The structure of a [see formula in PDF]-fullerene [see formula in PDF] with connectivity [see formula in PDF] can be determined by only three parameters [see formula in PDF], [see formula in PDF] and[see formula in PDF], thus we denote it by [see formula in PDF], where [see formula in PDF] is the radius (number of rings), [see formula in PDF] is the size (number of spokes in each layer, [see formula in PDF], [see formula in PDF] is even), and [see formula in PDF] is the torsion ([see formula in PDF]). In this paper, the counting formula of the perfect matchings in [see formula in PDF]is given, and the number of perfect matchings is obtained. Therefore, the correctness of the conclusion that every bridgeless cubic graph with [see formula in PDF] vertices has at least [see formula in PDF] perfect matchings proposed by Esperet et al is verified for [see formula in PDF]-fullerene [see formula in PDF].
BibTeX
@inproceedings{yang2023number,
  author = {Rui Yang and Mingzhu Yuan},
  title = {{The Number of Perfect Matchings in (3,6)-Fullerene}},
  booktitle = {Wuhan},
  year = {2023},
  doi = {10.1051/wujns/2023283192},
}
The Number of Perfect Matchings of {(3,4),4}-fullereneInternational Journal of Mathematics Trends and Technology · 2022
A bound on the number of perfect matchings in Klee-graphsDiscret. Math. Theor. Comput. Sci · 2013
k - Resonance of the Cartesian Product Graph P3 * CnInternational Journal of Mathematics Trends and Technology · 2023
Calculating the Determinant of the Adjacency Matrix and Counting Kekulé Structures in CirculenesZeitschrift · 1994
The Hosoya index and the Merrifield–Simmons indexJournal of Mathematical Chemistry · 2018
Wiener Indices of Balanced Binary TreesLecture Notes in Computer Science · 2005
Figure