0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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
    Commented Jun 23, 2015 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
    Commented Jun 23, 2015 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
    Commented Jun 23, 2015 at 19:05

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 24, 2015 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
    Commented Jun 24, 2015 at 9:06
  • $\begingroup$ If your upper limit is $n=10$, then it should be very easy. $\endgroup$
    – Gordon Royle
    Commented Jun 24, 2015 at 9:37
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! The sequence A126100 in the OEIS helped me a lot. $\endgroup$
    – Dominik Sieber
    Commented Jun 24, 2015 at 9:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .