Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

(Crossposted from math.stackexchange.)

Studying all 3-regular graphs that have only faces with 5 edges or more (simplified), I empirically found (computer program) that many hypothetically possible graphs, that by Euler's identity may exist ($F5 = 12 + F7 + 2F8 + 3F9 + ...$), do not actually exist. Using a VF2 algorithm to filter out isomorphic maps being created, I also noticed that not so many graphs as I expected exist. And that one general category of graphs, that always represents a simplified 3-regular graph, is that of fullerenes (with 12 faces F5 and an arbitrary number of F6). Here is a list of what I found, so far, for each class of graphs, from 12 faces to 20 faces (surrounding area included).

The question is: Since the computation of maps with 17, 18, 19, 20 faces (simplified and not containing isomorphic graphs) it is taking very long time (days of CPU time on a PC), is this sequence already known?

  • 12 faces: 1 (only 1 graph exists)
    • On 3 dimentional space (sphere) it is a dodecahedron
    • It is a fullerene: 20-fullerene Dodecahedral graph
  • 13 faces: 0 (no simplified graphs exist with 13 faces)
    • The hypothetical (by Euler's identity) map of 12 F5 and 1 F6 does not exist
  • 14 faces: 1 (12 F5 + 2 F6)
    • he hypothetical (by Euler's identity) map of 13 F5 and 1 F7 does not exist
    • It is a fullerene: GP (12,2) Generalized Petersen graph
  • 15 faces: 1 (12 F5 + 3 F6)
    • The hypothetical (by Euler's identity) map of 14 F5 and 1 F8 does not exist
    • It is a fullerene: 26-Fullerene
  • 16 faces: 3 (Two graphs are 12 F5 + 4 F6. The other has 14 F5 + 2 F7)
    • The hypothetical (by Euler's identity) map of 14 F5 and 2 F7 does exists
    • The other two are Fullerenes
  • 17 faces: ???
  • 18 faces: ???
  • 19 faces: ???
  • 20 faces: ???

ADD (28/Jan/2013):

share|improve this question
    
The m.se question was math.stackexchange.com/questions/287023/… –  Gerry Myerson Jan 29 '13 at 4:32
add comment

1 Answer

up vote 5 down vote accepted

Use Brinkmann & McKay's program "plantri"...

You will discover that there are

3 on 16 faces (as you said), 4 on 17 faces, 12 on 18 faces, 23 on 19 faces, 73 on 20 faces

and then going to Sloane's online encylopaedia you discover

https://oeis.org/A081621

So in short, the answer to your question is "yes, the sequence is fairly well known".

share|improve this answer
    
Thanks. So fast! I'm going to try this program right away. –  Mario Stefanutti Jan 29 '13 at 9:58
    
Thanks again. Plantri is really a great program and it is so fast. Where my program takes 1 minute to elaborate all graphs of 15 faces, Plantri is istantaneous. –  Mario Stefanutti Feb 8 '13 at 22:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.