0
$\begingroup$

We look for the property that a graph is both planar and has a trivial automorphism group.

How many non-isomorphic $n$-vertex graphs have such property and is there an $O(n^\beta)$ (at least randomized) algorithm to construct say $\alpha\cdot n$ such graphs for some fixed $\alpha,\beta>0$?

$\endgroup$
1
$\begingroup$

Consider this family of graphs which is very far from optimal but gives much more than you request: Let $n=3m+r$ and take a path of length $k=2m+r$ with vertices numbered in the obvious way and a pendant edge hanging from $m$ of the vertices including vertex $4$, vertex $k-2$ and $m-2$ more vertices between them. This gives an exponential of pair-wise non-isomorphic graphs.

LATER The number of trees on $n$ unlabeled nodes is asymptotically $C\alpha^nn^{-5/2}$ for constants $c \approx 0.535$ and $\alpha \approx 2.96$ Of course these are planar though most do have non-trivial automorhisms. However there are many subclasses with exponential growth which have only trivial automorphisms. One is trees with a single vertex of degree greater than 2 which is the common end of three or more paths all having distinct lengths.

The ones described above do have trivial automorphism group because there is a unique path of maximal length, one end it at distance two from a degree $3$ vertex and the other is at distance $4.$ Here is an illustration for $n=24$ the $5$ red edges can be placed in any of the $\binom{10}{5}=252$ possible ways among the inner $10$ vertices.

enter image description here

We could extend this to $$\sum_{j=0}^{\lfloor m/2 \rfloor}\binom{m-j}{j}$$ $m=n-9$ and $j$ "red" edges are placed in any possible way on $m-j$ inner vertices with $4+5$ on the ends destroying any automorphisms. Of course we could also replace red edges with paths of various lengths or other rooted trees with trivial automorphism groups.

But there is no reason to stick with trees. The green graph below is essentially a dodecahedron with $20$ vertices, $30$ edges and $120$ automorphisms. Adding just the internal red edge reduces that to two automorphisms, just the outer one reduces to $6$, and both together (so $21$ vertices and $32$ edges) leave no automorphisms. With that one can wildly add squares triangles and other cycles hanging off edges along with paths of various lengths (or more general automorphism free rooted trees) hanging off vertices and other decorations. It is possible to create non-trivial automorphisms but easy to avoid doing so.

enter image description here

$\endgroup$
1
  • $\begingroup$ do they have a trivial automorphism group? $\endgroup$
    – Mr.
    Jul 16 '16 at 13:38

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.