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

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

Offset: 0

Author

Gus Wiseman, Apr 23 2024

Keywords

• nonn
• more

Comments

The unlabeled version is A372169.

Examples

			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
		

Links

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

Crossrefs

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.

Programs

Mathematica

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}]

Formula

Binomial transform is A213434.