Premium
At least half of the leapfrog fullerene graphs have exponentially many Hamilton cycles
Author(s) -
Kardoš František,
Mockovčiaková Martina
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22660
Subject(s) - fullerene , planar graph , combinatorics , hexagonal crystal system , mathematics , graph , cubic graph , outerplanar graph , planar , line graph , discrete mathematics , voltage graph , computer science , physics , chemistry , crystallography , quantum mechanics , computer graphics (images)
A fullerene graph is a 3‐connected cubic planar graph with pentagonal and hexagonal faces. The leapfrog transformation of a planar graph produces the dual of the truncation of the given graph. A fullerene graph is a leapfrog if it can be obtained from another fullerene graph by the leapfrog transformation. We prove that leapfrog fullerene graphs on n = 12 k − 6 vertices have at least 2 k Hamilton cycles.