Take the 2-minute tour ×
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.

At Wikipedia I found that "according to a strengthened version of Frucht's theorem, there are infinitely many asymmetric cubic graphs".

Are there infinitely many asymmetric planar cubic graphs, too?

If so, does it follow that there is an infinite asymmetric planar cubic graph?

If so, how could this graph be characterized?

Background

I am looking for an homogeneous and isotropic (in the large) regular graph that could "mimick" a discretized plane (without distinguished directions as in a grid). So an infinite asymmetric 4-regular graph would be even better (reflecting dimension 2).

share|improve this question

2 Answers 2

up vote 5 down vote accepted

Unless I'm mistaken, you can add a sufficiently large "cyclic ladder" to the Frucht graph as in: alt text

I would argue that, in an automorphism, the right-hand side would need to be mapped to itself. Therefore, an automorphism of the above graph would imply an automorphism of the Frucht graph (and therefore must be trivial).

An infinite version could be constructed by appending two infinite ladders instead (actually, I'm pretty sure you could attach one infinite ladder).

share|improve this answer
    
Nice construction! But to be honest I was looking for an APCG that paves the plane a bit more "uniformly". Look at the Frucht graph here (en.wikipedia.org/wiki/File:Frucht_graph.dot.svg) and imagine it "uniformly continued" in all directions. –  Hans Stricker Nov 18 '10 at 9:11
    
By the way: How did you draw this graph? –  Hans Stricker Nov 18 '10 at 14:45
    
In paintbrush (: –  Douglas S. Stones Nov 18 '10 at 22:04

I am not sure if this gets at what you mean for the 4-valent case:

Take the infinite graph 4-valent which arises from tiling the plane with 4-gons (squares). Pick one vertex and remove that vertex and the 4 edges attached to it. (We now have four 3-valent vertices.) Join pairs of these 3-valent vertices with two edges each having slope 1. We now have a 4-valent infinite graph with two new 3-gons and a single 6-gon. We can get an asymmetric infinite graph be carrying out this process in various unsymmetrical locations of the original tiling. By starting with irregularly spaced lines (rectangles rather than squares) the two new added edges will have very different directions.

share|improve this answer

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.