[seqfan] Identifying sequence in Quanta Magazine graph theory article

William Orrick will.orrick at gmail.com
Tue Feb 21 19:25:31 CET 2023

*Quanta* had an article last week,


on a recent paper by Vogtmann and Borinski on the moduli space of graphs. I
didn't understand much of the article, but there was some discussion in the
comments about how a sequence appearing in the article doesn't seem to be
in the OEIS (or in any of the papers linked to in the article).

The sequence values given are a(2) = 3, a(3) = 15, a(4) = 111, and a(10)
= 2314204852. These numbers seem to represent the number of graphs of a
given rank, which I gather means circuit rank. Graphs are allowed to have
loops and multiple edges, and presumably vertices of valence 0, 1, or 2 are
disallowed to keep the numbers finite. Whether the graphs have to be
connected or whether they have to be bridgeless is not clear. There is some
condition about fixing lengths of edges that I didn't understand.

Scratching a bit with pencil and paper, I was able to come up with three
graphs of circuit rank 2 if bridges are allowed, and two if bridges are
forbidden. For circuit rank three I could only find 11 if bridges are
allowed, and only 7 if bridges are forbidden. I was not able to locate any
sequences in the OEIS enumerating graphs by circuit rank,

Can anyone say what this is all about?

More information about the SeqFan mailing list