A345218 -id:A345218 - cp's OEIS frontend

A213434 a(n) is the number of labeled triangle-free simple graphs on n vertices.

1, 2, 7, 41, 388, 5789, 133501, 4682270, 246348115, 19213627145, 2198376297964, 365587270414697, 87628189849380625, 30044424979717359410, 14633141237888767056799, 10059886640779846047089825

Offset: 1

R. H. Hardin, Jun 11 2012

Former name: Number of n X n symmetric binary matrices with zero diagonal and no three-node loops x(i,j)*x(j,k)*x(k,i) = 1, i < j < k.
From Brendan McKay, Jun 11 2021: (Start)
EXP transform of A345218.
Labeled version of A006785. (End)
a(n) is the number of sign mappings X:([n] choose 2) -> {+,-} such that for any ordered 3-tuple aManfred Scheucher, Jan 05 2024

			Some solutions for n=4:
  0 1 0 0     0 1 1 0     0 1 0 0     0 0 1 1     0 1 0 0
  1 0 1 0     1 0 0 1     1 0 0 0     0 0 1 0     1 0 0 1
  0 1 0 1     1 0 0 1     0 0 0 1     1 1 0 0     0 0 0 0
  0 0 1 0     0 1 1 0     0 0 1 0     1 0 0 0     0 1 0 0

Tobias Boege and Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.
Falk Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 8c665c7.

Cf. A006785, A345218.

a(11)-a(13) added using tinygraph by Falk Hüffner, Jun 19 2018
a(14)-a(15) added using tinygraph by Falk Hüffner, Oct 28 2019
a(16) added by Brendan McKay, Sep 15 2020
Name changed to the one suggested by Falk Hüffner and Brendan McKay, Jun 11 2021

A372168 Number of triangle-free simple labeled graphs covering n vertices.

Original entry on oeis.org

1, 0, 1, 3, 22, 237, 3961, 99900, 3757153, 208571691, 16945953790, 1999844518737, 340422874696873, 83041703920313712, 28850117307732482737, 14191512425207950473867, 9829313296102303971441502

Offset: 0

Gus Wiseman, Apr 23 2024

The unlabeled version is A372169.

			The a(4) = 22 graphs are:
  12-34
  13-24
  14-23
  12-13-14
  12-13-24
  12-13-34
  12-14-23
  12-14-34
  12-23-24
  12-23-34
  12-24-34
  13-14-23
  13-14-24
  13-23-24
  13-23-34
  13-24-34
  14-23-24
  14-23-34
  14-24-34
  12-13-24-34
  12-14-23-34
  13-14-23-24

Eric Weisstein's World of Mathematics, Triangle-Free Graph

Dominated by A006129, unlabeled A002494.
For all cycles (not just triangles) we have A105784, unlabeled A144958.
Covering case of A213434 (column k = 0 of A372170, unlabeled A263340).
The connected case is A345218, unlabeled A024607.
Column k = 0 of A372167, unlabeled A372173.
The unlabeled version is A372169.
For a unique triangle we have A372171, non-covering A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A054548 counts covering graphs by number of edges, unlabeled A370167.
Cf. A000272, A053530, A121251, A367862, A367863, A372191, A372174, A372175.

cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Union@@#==Range[n]&&Length[cys[#]]==0&]],{n,0,5}]

Binomial transform is A213434.

A345248 Number of labeled connected simple graphs on n vertices without cycles of length 4.

Original entry on oeis.org

1, 1, 4, 28, 302, 4776, 106732, 3249352, 131290812, 6922560160, 470586936176, 40833342324864, 4482709905772936, 617622136930640128, 106013904370382120400, 22516967955697072408576, 5880701545642715236590608, 1877504184190590494772860928

Offset: 1

Brendan McKay, Jun 12 2021

From R. J. Mathar, Apr 03 2022 (Start)
The sequence contains the row sums of the number of labeled connected simple graphs on V vertices with E edges, the triangle with V>=0, E>=0:
;
;
1;
0  3  1;
0  0 16  12;
0  0  0 125  162    15;
0  0  0   0 1296  2580   900;
0  0  0   0    0 16807  47715   35595     6615 ;
0  0  0   0    0     0 262144 1006488  1270080   619920    90720;
0  0  0   0    0     0      0 4782969 23859108 44893170 39867660  15892065  1995840 ;
(End)

LOG transform of A345249.
A077269 counts isomorphism classes.
Cf. A345218.

cp's OEIS Frontend

A213434 a(n) is the number of labeled triangle-free simple graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A372168 Number of triangle-free simple labeled graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A345248 Number of labeled connected simple graphs on n vertices without cycles of length 4.

Views

Author

Keywords

Comments

Crossrefs