Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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.
|
|
|
|
