Contents Online

# Journal of Combinatorics

## Volume 8 (2017)

### Number 2

### A linear time algorithm for finding a maximum independent set of a fullerene

Pages: 255 – 287

DOI: http://dx.doi.org/10.4310/JOC.2017.v8.n2.a2

#### Authors

#### Abstract

A *fullerene* is an all carbon molecule that can be represented by a 3-regular planar graph with face sizes five or six. A subset $S$ of the vertices of a graph forms an independent set if the vertices of $S$ are pairwise non-adjacent. The problem of finding the size of a maximum *independent set* of a graph is NP-complete when restricted to 3-regular graphs. In contrast, for fullerenes we have designed an algorithm that solves the problem in linear time.

#### Keywords

maximum independent set algorithm, fullerenes

#### 2010 Mathematics Subject Classification

Primary 05C69, 05C85. Secondary 05C10.