Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



A decision problem about 13 integers
Posted:
Jul 21, 1996 7:48 PM


A fullerene is a planar, cubic graph in which every face is a pentagon or a hexagon.
A fullerene is spiral if its faces can be drawn in a spiral sequence of pentagons and hexagons so each new face (after the second) shares an edge with its immediate predecessor in the spiral and with the first face in the preceding spiral that has an edge with a vertex of degree less than 3,[A].
A spiral fullerene is decribed by 12 integers, because every fullerene has exactly 12 pentagonal faces. Suppose that we have 13 integers, the first 12 of which describe a spiral fullerene, and the 13th is k. Let S be the decision problem in which we ask if the resulting fullerene has an independent set with k vertices.
Can one prove that S belongs to NP, or that it does not belong to P? Note that the size of the problem is logk, where k is the largest of the first 12 integers.
I would like to ask a similar question for arbitrary fullerenes. This would be possible if for example every fullerene could be fully described by distances between its pentagonal vertices, or any other bounded set of integers invariants. This question is anyway of interest for its own sake.
Siemion Fajtlowicz.
[A] P. W. Fowler and D. E. Manolopoulos, An Atlas of Fullerenes.



