2
$\begingroup$

A cubic graph is a graph, whose vertices are all of degree 3. A bicubic graph is a cubic graph that is bipartite.

The picture below shows the smallest bicubic graph. The only one with 6 vertices.

enter image description here

It's easy to notice that every bicubic graph has an even number of vertices. My question is: how many bicubic graphs of n vertices are there?

$\endgroup$
  • 4
    $\begingroup$ See OEIS sequence A008325. Since this sequence has keyword "hard" and the Data only goes up to $n=14$, it seems there isn't a simple answer to your question. $\endgroup$ – Robert Israel Sep 25 '17 at 20:24
0
$\begingroup$

Just like @Robert said in the comment, the problem is hard. The only known solution is up to n = 28:

n  bicubic(n)
6  1
8  1
10 2
12 6
14 14
16 41
18 157
20 725
22 4196
24 29816
26 246644
28 2297075
30 23503477
32 260265023
$\endgroup$
  • 1
    $\begingroup$ As it happens, OEIS already contained the necessary information that standard techniques suffice to add 30 23503477 and 32 260265023 to that list. $\endgroup$ – Peter Taylor Sep 28 '17 at 22:45

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.