OFFSET
1,2
COMMENTS
The circuit rank r(G) of a simple graph G is the minimum number of edges that must be removed to break all of its cycles. r(G) = m - n + c where m,n,c are the number of edges, vertices, and connected components respectively of G.
Equivalently, T(n,k) is the number of simple labeled graphs on [n] such that the incidence matrix has nullity equal to k where the incidence matrix is viewed as a matrix with entries in the field GF(2).
REFERENCES
R. Diestel, Graph Theory, Springer, 2017, pp. 23-27.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1160 (rows 1..20)
Wikipedia, Circuit rank.
Wikipedia, Incidence matrix.
FORMULA
T(n,0) = A001858(n).
E.g.f. for T(n,1): f(x)*g(x) where f(x) is the e.g.f. for A001858 and g(x) is the e.g.f. for A057500.
E.g.f.: exp(y*log(Sum_{k>=0} (1+y)^binomial(k,2)*(x/y)^k/k!)). - Andrew Howroyd, Jun 09 2025
EXAMPLE
Triangle T(n,k) begins:
1;
2;
7, 1;
38, 19, 6, 1;
291, 317, 235, 125, 45, 10, 1;
2932, 5582, 7120, 6915, 5215, 3057, 1371, 455, 105, 15, 1;
...
MATHEMATICA
Needs["Combinatorica`"]; Map[Select[#, # > 0 &] &, Transpose[ Table[ Table[ Total[ Map[#[[1]] &, Select[Table[{n!/GraphData[{n, i}, "AutomorphismCount"], GraphData[{n, i}, "CyclomaticNumber"]}, {i, 1, NumberOfGraphs[n]}], #[[2]] == k &]]], {n, 1, 7}], {k, 0, 15}]]] // Grid
PROG
(PARI) T(n)={[Vecrev(p)| p<-Vec(-1+serlaplace(exp(y*log(sum(k=0, n, (1+y)^binomial(k, 2)*x^k/k!/y^k, O(x*x^n))))))]}
{ foreach(T(7), row, print(row)) } \\ Andrew Howroyd, Jun 09 2025
CROSSREFS
KEYWORD
nonn,tabf,changed
AUTHOR
Geoffrey Critzer, Apr 20 2024
EXTENSIONS
More terms from Andrew Howroyd, Jun 09 2025
STATUS
approved