Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

(Crossposted to mathoverflow.net)

http://mathoverflow.net/questions/120162/question-about-3-regular-graphs-with-a-restriction-also-fullerene-and-four-color

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
Have you checked OEIS? BTW +1 cool question. add the chemistry-tag...;-) I would expect 17 and 19 to have no graphs... – draks ... Jan 25 at 23:32
I did a quick check but for now the sequence 1,0,1,1,3 has 252 match. I suppose still too few elements! – Mario Stefanutti Jan 25 at 23:39
... OEIS 1,0,1,1,3,0,_,0... – draks ... Jan 25 at 23:40
1  
With 17 and 19 faces for sure fullerene exist: hog.grinvin.org/Fullerenes – Mario Stefanutti Jan 25 at 23:41
cool, I just thought about assuming Barnette conjecture and using grinberg's theorem to exclude some cases, but (i) it seems obsolete now and (ii) I gotta go. Good nite... – draks ... Jan 25 at 23:49

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.