cp's OEIS Frontend

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

%I A372168 #10 Feb 16 2025 08:34:06
%S A372168 1,0,1,3,22,237,3961,99900,3757153,208571691,16945953790,
%T A372168 1999844518737,340422874696873,83041703920313712,28850117307732482737,
%U A372168 14191512425207950473867,9829313296102303971441502
%N A372168 Number of triangle-free simple labeled graphs covering n vertices.
%C A372168 The unlabeled version is A372169.
%H A372168 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Triangle-FreeGraph.html">Triangle-Free Graph</a>
%F A372168 Binomial transform is A213434.
%e A372168 The a(4) = 22 graphs are:
%e A372168   12-34
%e A372168   13-24
%e A372168   14-23
%e A372168   12-13-14
%e A372168   12-13-24
%e A372168   12-13-34
%e A372168   12-14-23
%e A372168   12-14-34
%e A372168   12-23-24
%e A372168   12-23-34
%e A372168   12-24-34
%e A372168   13-14-23
%e A372168   13-14-24
%e A372168   13-23-24
%e A372168   13-23-34
%e A372168   13-24-34
%e A372168   14-23-24
%e A372168   14-23-34
%e A372168   14-24-34
%e A372168   12-13-24-34
%e A372168   12-14-23-34
%e A372168   13-14-23-24
%t A372168 cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
%t A372168 Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Union@@#==Range[n]&&Length[cys[#]]==0&]],{n,0,5}]
%Y A372168 Dominated by A006129, unlabeled A002494.
%Y A372168 For all cycles (not just triangles) we have A105784, unlabeled A144958.
%Y A372168 Covering case of A213434 (column k = 0 of A372170, unlabeled A263340).
%Y A372168 The connected case is A345218, unlabeled A024607.
%Y A372168 Column k = 0 of A372167, unlabeled A372173.
%Y A372168 The unlabeled version is A372169.
%Y A372168 For a unique triangle we have A372171, non-covering A372172.
%Y A372168 A000088 counts unlabeled graphs, labeled A006125.
%Y A372168 A001858 counts acyclic graphs, unlabeled A005195.
%Y A372168 A054548 counts covering graphs by number of edges, unlabeled A370167.
%Y A372168 Cf. A000272, A053530, A121251, A367862, A367863, A372191, A372174, A372175.
%K A372168 nonn,more
%O A372168 0,4
%A A372168 _Gus Wiseman_, Apr 23 2024