# Generate all non-isomorphic partitions $\pi = \{ \{1, …, n-1\}, \{n\} \}$ for all graphs of order $n$

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?

• This sounds like a graph reconstruction problem. What will you do with such a deck (set or multiset) of partitions? – The Masked Avenger Jun 23 '15 at 16:24
• Note that these objects are equivalent to ordered partitions of graphs on 1 fewer vertex (up to isomorphism) by taking the neighbours of the distinguished vertex to be the members of the first part. – Ben Barber Jun 23 '15 at 17:06
• So, you want to count the number of isomorphism classes of connected graphs on $n$ vertices, with one distinguished vertex? – Per Alexandersson Jun 23 '15 at 19:05

I am not sure why you would want to generate these objects, but you could use geng to generate connected graphs, then nauty to compute the automorphism group of each graph, find the orbits of the group and then take one representative from each orbit. Each different orbit representative $v$ of $\text{Aut}(G)$ then gives you one "pointed graph" $(G,v)$, which seems to be what you want.
• Thank you both so much! I am interested in a leader-follower consensus problem as described in here. I want to run some complete simulations for $n\leq10$ to get a quantitative statement about the uncontrollable subspaces for small graphs. – Dominik Sieber Jun 24 '15 at 9:06
• If your upper limit is $n=10$, then it should be very easy. – Gordon Royle Jun 24 '15 at 9:37
The number of unlabeled connected graphs on $n$ vertices with a marked vertex is Sequence A126100 in the OEIS. The first few values (starting with $n=0$) are 0, 1, 1, 3, 11, 58, 407, 4306, 72489, 2111013, 111172234.