A334275 Number of unlabeled connected graphs with n vertices such that every vertex has exactly 2 vertices at distance 2.

1, 0, 0, 0, 0, 1, 11, 9, 7, 5, 6, 7, 10, 11, 14, 18, 22, 26, 34, 40, 50, 61, 74, 89, 111, 131, 159, 192, 231, 274, 332, 392, 469, 557, 661, 780, 928, 1088, 1285, 1511, 1776, 2076, 2439, 2843, 3324, 3873, 4511, 5238, 6096, 7057, 8183, 9466

Offset

0,7

Comments

Gaar and Krenn call these graphs 2-metamour-regular.

Links

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

E. Gaar and D. Krenn, Metamour-regular Polyamorous Relationships and Graphs, arXiv:2005.14121 [math.CO], 2020.

Formula

a(n) = p_3(n) + 1 for n >= 9 with p_3(n) being the number of integer partitions of n with parts at least 3 (A008483).

Example

For n = 8 vertices, there exist the connected 2-metamour-regular graphs
   - c(C_8), c(C_5) join c(C_3), c(C_4) join c(C_4),
   - C_8 and
   - 3 exceptional graphs,
where C_i is the cycle graph on i vertices, and c(G) is the complement graph of G.
Therefore the unlabeled total is a(8) = 7.

Prog

(SageMath) [(len(Partitions(n, min_part=3)) if n >= 6 else 0)
           + (1 if n >= 5 else 0)
           + {0: 1, 6: 8, 7: 6, 8: 3}.get(n, 0)
           for n in srange(52)]
(PARI) a(n)=if(n<9, [1, 0, 0, 0, 0, 1, 11, 9, 7, 5][n+1], numbpart(n)-numbpart(n-1)-numbpart(n-2)+numbpart(n-3)+1) \\ Charles R Greathouse IV, Apr 22 2020

Crossrefs

Cf. A008483.

Sequence in context: A038322 A299972 A378899 * A090075 A004500 A342162

Adjacent sequences: A334272 A334273 A334274 * A334276 A334277 A334278

Keyword

nonn

Author

Daniel Krenn, Apr 21 2020

Status

approved