Let $G$ be any connected, undirected, and unweighted graph of order $n$. Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster and 1 vertex is in the second cluster.

How many non-isomorphic partitions $\pi$ of all graphs $G$ of order $n$ are there? How can one compute them all efficiently?

To illustrate the problem an easy example: for $n=3$, all 3 possible non-isomorphic partitions are depicted in the following figure (https://i.sstatic.net/Bv6h0.png) White vertices belong to the first cluster $C_1$ and the black vertex to the second cluster $C_2$

However, the following graph 4 is isomorphic to graph 3 (https://i.sstatic.net/v1fke.png)

Any idea how I can approach that problem in a computationally efficient way by e.g. using geng from nauty/trace. Any help would be very helpful.

Let $G$ be any connected, undirected, and unweighted graph of order $n$. Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster and 1 vertex is in the second cluster.

How many non-isomorphic partitions $\pi$ of all graphs $G$ of order $n$ are there? How can one compute them all efficiently?

To illustrate the problem an easy example: for $n=3$, all 3 possible non-isomorphic partitions are depicted in the following figure.

White vertices belong to the first cluster $C_1$ and the black vertex to the second cluster $C_2$

However, the following graph 4 is isomorphic to graph 3,

Any idea how I can approach that problem in a computationally efficient way by e.g. using geng from nauty/trace?