1
$\begingroup$

Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal to this:

My questions are:

  1. Does there exist a C3CBP graph on $n$ vertices for every even $n > n_0$ where $n_0$ is some small constant?
  2. Does there exist a C3CBP graph without any non trivial automorphisms on $n$ vertices for every even $n > n_1$ where $n_1$ is some small constant?

Notice that $3$-connected planar graphs have only at most linear sized automorphism groups so the second question is natural.

I need the existence and explicit construction of such graphs in an algorithmic problem apparently unrelated to Barnette’s conjecture.

$\endgroup$
2
$\begingroup$

I have a partial solution, with constructions for the first question and for the second question when $n = 2\ (\text{mod}\ 4)$.

Here are constructions for $n = 8$ and $n = 14$. These generalise to constructions for $n = 0\ (\text{mod}\ 4)$ and $n = 2\ (\text{mod}\ 4)$, by taking any square, for example 1,2,3,6 in the second construction, and replacing it with a ladder like shown in the third image.

For the second question, the $2\ (\text{mod}\ 4)$ construction has no nontrivial automorphisms when $n \geq 18$, as we can recover the labeling. First find the added ladder and the pairs 1-2 and 3-6. To discern between them, note that the nodes 1 and 2 are not in any four-node cycle except in the ladder, while 1 and 6 are. Similarly 2 and 3 are not in a four-node cycle except in the ladder, while 1 and 6 are. Then you can uniquely discern 4 (only non-ladder node connected to 1), 5 (same for 6), 8 (only node connected to 3 and 5) and so on.

construction for 0 mod 4 construction for 2 mod 4 construction for 2 mod 4 with ladder

| cite | improve this answer | |
$\endgroup$

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.