A372176 - OEIS

A372176

Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs on n vertices with exactly 2k directed cycles of length > 2.

1, 1, 2, 7, 1, 38, 19, 0, 6, 0, 0, 0, 1, 291, 317, 15, 220, 0, 0, 70, 55, 0, 0, 0, 0, 30, 15, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

A directed cycle in a simple (undirected) graph is a sequence of distinct vertices, up to rotation, such that there are edges between all consecutive elements, including the last and the first.

LINKS

Table of n, a(n) for n=0..50.

EXAMPLE

Triangle begins (zeros shown as dots):

7 1

38 19 . 6 ... 1

291 317 15 220 .. 70 55 .... 30 15 ........ 10 ............... 1

The T(4,3) = 6 graphs:

12,13,14,23,24

12,13,14,23,34

12,13,14,24,34

12,13,23,24,34

12,14,23,24,34

13,14,23,24,34

MATHEMATICA

cyc[y_]:=Select[Join@@Table[Select[Join@@Permutations/@Subsets[Union@@y, {k}], And@@Table[MemberQ[Sort/@y, Sort[{#[[i]], #[[If[i==k, 1, i+1]]]}]], {i, k}]&], {k, 3, Length[y]}], Min@@#==First[#]&];

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Length[cyc[#]]==2k&]], {n, 0, 4}, {k, 0, Length[cyc[Subsets[Range[n], {2}]]]/2}]

CROSSREFS

Column k = 0 is A001858 (unlabeled A005195), covering A105784.

Row lengths are A002807 + 1.

Row sums are A006125, unlabeled A000088.

Counting edges instead of cycles gives A084546 (covering A054548), unlabeled A008406 (covering A370167).

Counting triangles instead of cycles gives A372170 (covering A372167), unlabeled A263340 (covering A372173).

The covering case is A372175.

Column k = 1 is A372193 (covering A372195), unlabeled A236570.

A006129 counts graphs, unlabeled A002494.

A322661 counts covering loop-graphs, unlabeled A322700.