We explore the relationship between Kekulé structures and maximum face independence sets in fullerenes: plane trivalent graphs with pentagonal and hexagonal faces. For the class of leap-frog fullerenes, we show that a maximum face independence set corresponds to a Kekulé structure with a maximum number of benzene rings and may be constructed by partitioning the pentagonal faces into pairs and 3-coloring the faces with the exception of a very few faces along paths joining paired pentagons. We also obtain some partial results for non-leap-frog fullerenes.
|Original language||English (US)|
|Number of pages||16|
|Journal||European Journal of Combinatorics|
|State||Published - May 2007|
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics