Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: A decision problem about 13 integers
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
siemion fajtlowicz,

Posts: 29
Registered: 12/12/04
A decision problem about 13 integers
Posted: Jul 21, 1996 7:48 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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.







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.