Fullerenes are all-carbon molecules with polyhedral structures where each atom is bonded with three other atoms and the faces of the polyhedron are pentagons and hexagons. Fullerene graphs model the fullerene structures and are cubic planar graphs having twelve pentagonal faces and the remaining faces are hexagonal. This work explores two models that seek to determine the maximum number of bulky addends that may bond to the surface of a fullerene.
The first model assumes that any two bulky addends are too large to bond to adjacent carbon atoms. This is equivalent to finding a graph-theoretical maximum independent set: a vertex subset of maximum size such that no two vertices are adjacent. The problem of determining the maximum independent set order is NP-hard for general cubic planar graphs and the complexity for the fullerene subclass was previously unknown. By extending the work of Graver, a graph-theoretical foundation is laid then used to derive a linear-time algorithm for solving the maximum independent set problem for fullerenes. A discussion of the relationship between maximum independent sets and some specific families of fullerenes follows.
The second model refines the first by adding an additional requirement that the resulting molecule is stable according to Hückel theory: the molecule exhibits a stable distribution of π electrons. The graph-theoretical description of this model is a maximum closed-shell independent set: a vertex subset of maximum size such that no two vertices are adjacent and exactly half of the eigenvalues of the adjacency matrix of the graph that results from the deletion of the vertex subset are positive. Computations for finding a maximum closed-shell independent set rely on determining whether fullerene subgraphs are closed-shell (satisfy the eigenvalue requirement) so a linear-time algorithm for finding the inertia (number of negative, zero, and positive eigenvalues) of unicyclic graphs is given. This algorithm is part of an exponential-time algorithm for finding a maximum closed-shell independent set of a fullerene molecule that is fast enough for practical use. An improved upper bound of 3n/8 + 3/2 for the closed-shell independence number is included.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1783 |
| Date | 06 October 2009 |
| Creators | Daugherty, Sean Michael |
| Contributors | Myrvold, W. J. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0147 seconds