Timeline for Enumeration of connected, bridgeless, trivalent graphs
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 20, 2020 at 12:30 | comment | added | Noam Zeilberger | following up to Sam Hopkins' comment, another related sequence is oeis.org/A267827, which counts isomorphism classes of rooted bridgeless trivalent maps on oriented surfaces of arbitrary genus, or equivalently, bridgeless trivalent graphs equipped with a rooting and a cyclic ordering of the half-edges around each vertex. | |
| Nov 20, 2020 at 9:06 | answer | added | Brendan McKay | timeline score: 2 | |
| Nov 20, 2020 at 5:34 | comment | added | luthien | Oh wow, okay. What is your strategy for computing these, may I ask? I'm not much of a combinatorialist. | |
| Nov 20, 2020 at 5:32 | comment | added | Brendan McKay | I did it just now. The next value is 3449683. | |
| Nov 20, 2020 at 4:52 | comment | added | luthien | @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? | |
| Nov 19, 2020 at 23:41 | comment | added | Brendan McKay | 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. | |
| Nov 19, 2020 at 22:05 | history | edited | luthien | CC BY-SA 4.0 |
added a link
|
| Nov 19, 2020 at 21:35 | comment | added | Dan Petersen | Do you know a paper of Hanlon and Robinson, "Counting bridgeless graphs"? | |
| Nov 19, 2020 at 19:17 | history | edited | luthien | CC BY-SA 4.0 |
added 192 characters in body
|
| Nov 19, 2020 at 17:14 | history | edited | luthien | CC BY-SA 4.0 |
removed extraneous information
|
| Nov 19, 2020 at 16:36 | comment | added | Sam Hopkins | 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. | |
| Nov 19, 2020 at 16:30 | history | asked | luthien | CC BY-SA 4.0 |