A372153 Irregular triangular array read by rows. T(n,k) is the number of simple labeled graphs on [n] with circuit rank equal to k, n >= 1, 0 <= k <= binomial(n-1,2).

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, 36961, 108244, 207130, 306775, 368046, 364539, 300342, 205940, 116910, 54362, 20356, 5985, 1330, 210, 21, 1, 561948, 2331108, 6176387, 12709760

Offset: 1

Author

Geoffrey Critzer, Apr 20 2024

Keywords

• nonn
• tabf

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).

Examples

			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;
  ...
		

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.

Crossrefs

Cf. A001858, A057500.

Programs

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

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

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

Extensions

More terms from Andrew Howroyd, Jun 09 2025