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: https://dx.doi.org/10.4310/JOC.2017.v8.n2.a2

Authors

Sean Daugherty (Department of Computer Science, University of Victoria, British Columbia, Canada)

Wendy Myrvold (Department of Computer Science, University of Victoria, British Columbia, Canada)

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.

Published 14 February 2017