A396149 Number of connected graphs on n vertices where every edge is part of at least one triangle.

1, 1, 0, 1, 2, 7, 31, 218, 2644, 62286, 2954024, 277508807, 50209732882

Offset

0,5

Comments

A connected graph satisfies this property if every edge belongs to at least one 3-clique (triangle). Equivalently, for every edge (u, v), there exists at least one vertex w such that both (u, w) and (v, w) are also edges in the graph.

Terms for n >= 8 were computed by the author using a custom MapReduce algorithm.

Links

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

Banri Ogawa, C++ program

Banri Ogawa, oeis-A396149-data, GitHub repository containing statistical data of various graph invariants for these graphs.

Example

For n = 3, the a(3) = 1 graph is the complete graph K_3.

Prog

(C++) // See Links
(PARI) a(n)={if(n<3, return(n<2)); my(E=concat(vector(n-1, i, vector(n-i, j, [i, i+j]))), R=List()); for(m=0, 2^#E-1, my(G=matrix(n, n)); for(e=1, #E, if(bittest(m, e-1), G[E[e][1], E[e][2]]=G[E[e][2], E[e][1]]=1)); if(vecmin(vecmin((matid(n)+G)^(n-1)))>0 && vecmin(vecmin(G^2-G))>=0, my(maxG=""); forperm(n, p, my(Gp=Str(matrix(n, n, i, j, G[p[i], p[j]]))); if(Gp>maxG, maxG=Gp)); listput(R, maxG))); #Set(R)}

Crossrefs

Cf. A001349.

Sequence in context: A365563 A365565 A091312 * A118581 A102159 A309164

Adjacent sequences: A396146 A396147 A396148 * A396150 A396151 A396152

Keyword

nonn,hard,more

Author

Banri Ogawa, May 18 2026

Extensions

a(12) from Sean A. Irvine, May 22 2026

Status

approved