Sandwiching saturation number of fullerene graphs
Journal
MATCH Commun. Math. Comput. Chem
Date Issued
2014-05-09
Author(s)
Vesna Andova
František Kardoš
Riste Škrekovski
Abstract
The saturation number of a graph $G$ is the cardinality of any smallest
maximal matching of $G$, and it is denoted by $s(G)$. Fullerene graphs are
cubic planar graphs with exactly twelve 5-faces; all the other faces are
hexagons. They are used to capture the structure of carbon molecules. Here we
show that the saturation number of fullerenes on $n$ vertices is essentially
$n/3$.
maximal matching of $G$, and it is denoted by $s(G)$. Fullerene graphs are
cubic planar graphs with exactly twelve 5-faces; all the other faces are
hexagons. They are used to capture the structure of carbon molecules. Here we
show that the saturation number of fullerenes on $n$ vertices is essentially
$n/3$.