Abstract | ||
---|---|---|
We consider the following question, motivated by the enumeration of fullerenes. A fullerene patch is a 2-connected plane graph G in which inner faces have length 5 or 6, non-boundary vertices have degree 3, and boundary vertices have degree 2 or 3. The degree sequence along the boundary is called the boundary code of G. We show that the question whether a given sequence S is a boundary code of some fullerene patch can be answered in polynomial time when such patches have at most five 5-faces. We conjecture that our algorithm gives the correct answer for any number of 5-faces, and sketch how to extend the algorithm to the problem of counting the number of different patches with a given boundary code. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-10631-6_76 | international symposium on algorithms and computation |
Keywords | DocType | Volume |
degree sequence,finding fullerene patches,fullerene patch,inner face,non-boundary vertex,2-connected plane graph,boundary vertex,polynomial time,following question,different patch,correct answer,boundary code | Journal | abs/0907.2627 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.45 |
References | Authors | |
7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paul Bonsma | 1 | 287 | 20.46 |
Felix Breuer | 2 | 22 | 5.35 |