A236570 -id:A236570 - cp's OEIS frontend

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

1, 0, 1, 3, 1, 19, 15, 0, 6, 0, 0, 0, 1, 155, 232, 15, 190, 0, 0, 70, 50, 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

Offset: 0

Gus Wiseman, Apr 24 2024

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.

			Triangle begins (zeros shown as dots):
  1
  .
  1
  3 1
  19 15 . 6 ... 1
  155 232 15 190 .. 70 50 .... 30 15 .......... 10 .............. 1
Row n = 4 counts the following graphs:
  12,34     12,13,14,23  .  12,13,14,23,24  .  .  .  12,13,14,23,24,34
  13,24     12,13,14,24     12,13,14,23,34
  14,23     12,13,14,34     12,13,14,24,34
  12,13,14  12,13,23,24     12,13,23,24,34
  12,13,24  12,13,23,34     12,14,23,24,34
  12,13,34  12,13,24,34     13,14,23,24,34
  12,14,23  12,14,23,24
  12,14,34  12,14,23,34
  12,23,24  12,14,24,34
  12,23,34  12,23,24,34
  12,24,34  13,14,23,24
  13,14,23  13,14,23,34
  13,14,24  13,14,24,34
  13,23,24  13,23,24,34
  13,23,34  14,23,24,34
  13,24,34
  14,23,24
  14,23,34
  14,24,34

Row lengths are A002807 + 1.
Row sums are A006129, unlabeled A002494.
Column k = 0 is A105784 (for triangles A372168, non-covering A213434), unlabeled A144958 (for triangles A372169).
Counting triangles instead of cycles gives A372167 (non-covering A372170), unlabeled A372173 (non-covering A263340).
The non-covering version is A372176.
Column k = 1 is A372195 (non-covering A372193, for triangles A372171), unlabeled A372191 (non-covering A236570, for triangles A372174).
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000272, A053530, A121251, A137916, A137917, A372172, A372194.

cycles[g_]:=Join@@Table[Select[Join@@Permutations /@ Subsets[Union@@g,{k}],Min@@#==First[#]&&And@@Table[MemberQ[Sort/@g,Sort[{#[[i]], #[[If[i==k,1,i+1]]]}]],{i,k}]&],{k,3,Length[g]}];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[cycles[#]]==2k&]], {n,0,5},{k,0,Length[cycles[Subsets[Range[n],{2}]]]/2}]

A372194 Number of unlabeled graphs with n vertices and a unique triangle.

Original entry on oeis.org

0, 0, 0, 1, 2, 7, 23, 102, 526, 3624, 32240, 382095, 5986945

Offset: 0

Gus Wiseman, Apr 24 2024

The labeled version is A372172.

			Representatives of the a(3) = 1 through a(6) = 23 graphs:
    12,13,23    12,13,23       12,13,23             12,13,23
                14,23,24,34    12,34,35,45          12,34,35,45
                               14,23,24,34          14,23,24,34
                               12,25,34,35,45       12,25,34,35,45
                               14,25,34,35,45       12,36,45,46,56
                               15,25,34,35,45       13,23,45,46,56
                               12,14,25,34,35,45    14,25,34,35,45
                                                    15,25,34,35,45
                                                    12,14,25,34,35,45
                                                    12,23,36,45,46,56
                                                    13,23,36,45,46,56
                                                    13,25,36,45,46,56
                                                    13,26,36,45,46,56
                                                    14,25,36,45,46,56
                                                    15,26,36,45,46,56
                                                    16,26,36,45,46,56
                                                    12,13,25,36,45,46,56
                                                    12,13,26,36,45,46,56
                                                    13,23,25,36,45,46,56
                                                    14,23,25,36,45,46,56
                                                    16,23,25,36,45,46,56
                                                    13,14,23,25,36,45,46,56
                                                    13,15,23,25,36,45,46,56

Gus Wiseman, The a(3) = 1 through a(6) = 23 graphs with a unique triangle.

For no triangles we have A006785, covering A372169.
Column k = 1 of A263340, covering A372173.
The labeled version is A372172.
The covering case is A372174, labeled A372171.
For all cycles (not just triangles): A236570, A372193, A372191, A372195.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A002494 counts unlabeled covering graphs, labeled A006129.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A137917, A137918, A140637, A144958, A213434, A372168, A372170.

geng $n | countg -T1 # Georg Grasegger, Aug 03 2024

First differences are A372174.

a(11)-a(12) added by Georg Grasegger, Aug 03 2024

A291648 a(n) is the number of simple graphs of order n having at most one cycle (such graphs are called "at most unicyclic graphs").

Original entry on oeis.org

1, 2, 4, 9, 19, 45, 105, 261, 657, 1708, 4498, 12081, 32752, 89792, 247893, 689004, 1924357, 5398587, 15197830, 42917215, 121507597, 344806293, 980423528, 2792741331, 7967842859, 22765631866, 65131178683, 186560990191, 53497417058, 1535637252938

Offset: 1

Louis V QUINTAS, Aug 28 2017

nonn

a(n) = A005195(n) + A236570(n). Proof: Since an at most unicyclic graph is either a forest or a unicyclic graph and since the latter two types of graphs have been enumerated (see A005195, A236570) the enumeration of the at most unicyclic graphs is the sum of the enumeration of the forests and unicyclic graphs, namely, the sum of the sequences A005195 and A236570, where these sequences start for n >= 1, respectively,
1, 2, 3, 6, 10, 20, 37, 76, ...
0, 0, 1, 3,  9, 25, 68 185, ... .

			For n = 4, a(4) = 6 + 3 = 9 and for n = 5, a(5) = 10 + 9 = 19

E. G. DuCasse, L. V. Quintas, and J. M. Zorluoglu, The At Most Unicyclic Random Graph Process, Mathematics Department, Pace University, New York, No. 1 (2017).

Cf. A005195 (number of forests with n unlabeled nodes), A236570 (number of n-node unicyclic graphs).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A372194 Number of unlabeled graphs with n vertices and a unique triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Formula

Extensions

A291648 a(n) is the number of simple graphs of order n having at most one cycle (such graphs are called "at most unicyclic graphs").

Views

Author

Keywords

Comments

Examples

Links

Crossrefs