2
$\begingroup$

Is it known how many connected, bridgeless, trivalent graphs there are on $2n$ vertices?

I am allowing the graph to have multiple edges, but no self edges (though I think the fact that the graph is trivalent and bridgeless rules out the possibility of self-edges). Here we say a graph is bridgeless if it does not contain any edges that would disconnect the graph if removed.

Edit: I have found a sequence for the number of connected, loopless, trivalent graphs on $2n$ vertices, which I believe is a super set of what I want (bridgeless $\Rightarrow$ loopless).

Improve this question
$\endgroup$
7
  • $\begingroup$ Maybe you'd be interested in oeis.org/A000260. Though it's more common in this area to count maps, which are graphs embedded in the sphere. $\endgroup$
    – Sam Hopkins
    Commented Nov 19, 2020 at 16:36
  • $\begingroup$ Do you know a paper of Hanlon and Robinson, "Counting bridgeless graphs"? $\endgroup$
    – Dan Petersen
    Commented Nov 19, 2020 at 21:35
  • 1
    $\begingroup$ For even orders 2, 4, ..., 18, the counts of isomorphism classes are 1, 2, 5, 16, 66, 365, 2602, 23811, 264993. Not in OEIS. It is plausible that labelled counts are present but I cant find them. I believe that "bridgeless" is the same as "2-connected" in this case. $\endgroup$
    – Brendan McKay
    Commented Nov 19, 2020 at 23:41
  • $\begingroup$ @BrendanMcKay Ah, I believe you are right about bridgeless being equivalent to 2-connected. The sequence does look correct. Do you have a reference for that? $\endgroup$
    – luthien
    Commented Nov 20, 2020 at 4:52
  • 1
    $\begingroup$ I did it just now. The next value is 3449683. $\endgroup$
    – Brendan McKay
    Commented Nov 20, 2020 at 5:32

1 Answer 1

Reset to default
2
$\begingroup$

This is about the generation problem, which is different from the theoretical enumeration problem.

One method, which is not efficient for large sizes is to use the tools geng and multig from nauty:

geng -CD3 16 | multig -m2r3 -u

counts 23811 mutltigraphs on 16 vertices in about 10 seconds. First the 2-connected simple graphs with maximum degree 3 are made, then some edges are doubled to make it cubic. Change "-u" to "-T" if you want to see the multigraphs. It takes over an hour for 20 vertices (mostly in the first step) which is not so good.

A faster method is to make connected cubic multigraphs and reject those which are not 2-connected. An example of code to generate connected cubic multigraphs is here. The linear test for 2-connectivity is unfortunately not included but will add very little to the generation time.

The counts up to order 20 are 1, 2, 5, 16, 66, 365, 2602, 23811, 264993, 3449683.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .