1
$\begingroup$

I saw this question: How to calculate the number of possible connected simple graphs with $n$ labelled vertices

But how can we count graphs with only one dominant vertex (only one vertex in graph that connected to each other node)?

Suppose that we had a set of vertices labelled 1,2,…,n.

In what efficient way do we be able to calculate the number of possible ways the graph can be made?

$\endgroup$

1 Answer 1

0
$\begingroup$

The answer is $n$ multiplied by the number of graphs on $n-1$ vertices with no dominant vertices.

How many graphs on $n$ vertices have no dominant vertices? this can be obtained via inclusion-exclusion, it yields $\sum\limits_{i=0}^n(-1)^i\binom{n}{i}2^{\binom{n-i}{2}}$

Hence the answer to your question is $n\sum\limits_{i=0}^{n-1}(-1)^i\binom{n-1}{i}2^{\binom{n-1-i}{2}}$

$\endgroup$
3
  • $\begingroup$ Is first formula for graph with all connected vertices? Because we can have situation where there is two independent graphs connected only by dominant vertex. $\endgroup$
    – Rick Lena
    Mar 30, 2021 at 17:26
  • $\begingroup$ This formula accounts for stars as well, I think that is what you are asking. $\endgroup$
    – Asinomás
    Mar 30, 2021 at 17:34
  • $\begingroup$ Yes, it is. Now everything fine. I just misunderstood at first. Thank you! $\endgroup$
    – Rick Lena
    Mar 30, 2021 at 17:43

You must log in to answer this question.

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