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

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

Table of n, a(n) for n=1..42.

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.

Example

    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

Crossrefs

Cf. A001858, A057500.

Sequence in context: A330914 A125699 A372176 * A372170 A369371 A242207

Adjacent sequences: A372150 A372151 A372152 * A372154 A372155 A372156

Keyword

nonn,more,tabf

Author

Geoffrey Critzer, Apr 20 2024

Status

approved