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

Author

Daniel Krenn, Apr 21 2020

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A008483.

Programs

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

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

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).