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?

  • 1
    $\begingroup$ This sounds like a graph reconstruction problem. What will you do with such a deck (set or multiset) of partitions? $\endgroup$ – The Masked Avenger Jun 23 '15 at 16:24
  • $\begingroup$ 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. $\endgroup$ – Ben Barber Jun 23 '15 at 17:06
  • 1
    $\begingroup$ So, you want to count the number of isomorphism classes of connected graphs on $n$ vertices, with one distinguished vertex? $\endgroup$ – 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.

  • $\begingroup$ Yes, this is the way to go. The most efficient method is to use a custom output routine for geng, which will get you about 5-10 million objects per second. $\endgroup$ – Brendan McKay Jun 24 '15 at 6:03
  • $\begingroup$ 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. $\endgroup$ – Dominik Sieber Jun 24 '15 at 9:06
  • $\begingroup$ If your upper limit is $n=10$, then it should be very easy. $\endgroup$ – 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.

  • $\begingroup$ Thank you! The sequence A126100 in the OEIS helped me a lot. $\endgroup$ – Dominik Sieber Jun 24 '15 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.