1
$\begingroup$

"According to a strengthened version of Frucht's theorem, there are infinitely many asymmetric cubic graphs." If there are any, what is the smallest cubic bipartite asymmetric graph?

Kind of a bipartite version of Frucht's graph. If there are none, why's that?

EDIT: The graph doesn't necessarily need to be planar, but $3$-edge-colorable...

$\endgroup$
3
$\begingroup$

There are 85 cubic graphs on 12 vertices and five of them are asymmetric, and all five are 3-edge colourable. No cubic graph on 10 vertices is asymmetric; I did not bother to check the graphs on eight vertices, because my recollection was that the smallest asymmetric regular graphs are on 12 vertices. (All computations in sage.)

$\endgroup$
  • $\begingroup$ How many of them are bipartite? $\endgroup$ – draks ... Jan 19 '15 at 6:23
  • $\begingroup$ Here they say that $5$ of them are bipartite. Can you confirm that? $\endgroup$ – draks ... Jan 21 '15 at 17:11
  • $\begingroup$ oh and here they are shown...only "$12$-cubic graph 66" looks asymmetric to me! $\endgroup$ – draks ... Jan 21 '15 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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