The independence numbers of fullerenes and benzenoids

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


We explore the structure of the maximum vertex independence sets in fullerenes: plane trivalent graphs with pentagonal and hexagonal faces. At the same time, we will consider benzenoids: plane graphs with hexagonal faces and one large outer face. In the case of fullerenes, a maximum vertex independence set may constructed as follows: (i)Pair up the pentagonal faces.(ii)Delete the edges of a shortest path in the dual joining the paired faces to get a bipartite subgraph of the fullerene.(iii)Each of the deleted edges will join two vertices in the same cell of the bipartition; eliminating one endpoint of each of the deleted edges results in two independent subsets. The main part of this paper is devoted to showing that for a properly chosen pairing, the larger of these two independent subsets will be a maximum independent set. We also prove that the construction of a maximum vertex independence set in a benzenoid is similar with the dual paths between pentagonal faces replaced by dual circuits through the outside face. At the end of the paper, we illustrate this method by computing the independence number for each of the icosahedral fullerenes.

Original languageEnglish (US)
Pages (from-to)850-863
Number of pages14
JournalEuropean Journal of Combinatorics
Issue number6
StatePublished - Aug 2006

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'The independence numbers of fullerenes and benzenoids'. Together they form a unique fingerprint.

Cite this