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. <img src="https://i.sstatic.net/Bv6h0.png" height="100" /> 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, <img src="https://i.sstatic.net/v1fke.png" height="100" /> Any idea how I can approach that problem in a computationally efficient way by e.g. using geng from nauty/trace?