Probability that a graph of order $n$ has a subgraph which is a star of order $n$.

Question

If a graph has $n$ vertices, is there a known expression for the probability that the graph will have as a subgraph a star with $n$ vertices? (I.e. if randomly sampled from the set of non-isomorphic graphs with $n$ vertices and any allowable number of edges).

Obviously, you can produce a not very tight bound using the probability of a graph being connected, but wondering if there were an exact known expression.

In particular if asymptotic results or exact results are known this would be great, but even good bounds would be interesting.

Answer 1

Define $k_m$ as the number of isomoprism classes of graphs on $m$ nodes.

Define $s_m$ as the number of isomorphism classes of graphs on $m$ nodes with a star, wi th $s_0=0,s_1=1$.

Then $s_n = \sum_{i=0}^{n-1} (k_i-s_i)$.

This is seen by taking an isomorphism class of graphs with $i$ nodes and no stars, and adding $n-i$ stars.

Writing:

$$s_n = (k_{n-1}-s_{n-1})+\sum_{i=0}^{n-2} (k_i-s_i) = k_{n-1}-\sum_{i=0}^{n-2} (k_i-s_i) + \sum_{i=0}^{n-2} (k_i-s_i)=k_{n-1}$$

So if you know the sequence $k_n$ your exact probability is $\frac{k_{n-1}}{k_n}$.

The non-isomorphic random graph sample is a highly unusual condition, because (1) it doesn't model any "real world" conditions, and (2) it tends to be very difficult.

From some of the references here: $$k_m\sim \frac{2^{\binom m 2}}{m!},$$ then your probability is $\sim \frac{n}{2^{n-1}}$.

---

If you abandon the non-isomorphic part, this is an inclusion-exclusion question. If the nodes are $\{1,2,\dots,n\}$, let $A_i$ be the number of graphs with a star at point $i$ - that is, where node $i$ is joined with all other nodes.

Then you want:

$$|A_1\cup A_2\cup \cdots \cup A_n|$$

Inclusion-exclusion gives:

$$|A_1\cup A_2\cup \cdots \cup A_n|=\sum_{k=1}^{n} (-1)^{k-1}\binom{n}{k}2^{\binom{n-k}2}$$

I doubt this has a nice cosed form.

Then the probability is this divided by $2^{\binom{n}{2}}$. You get the same asymptote $\frac{n}{2^{n-1}}$.

This is also why we don't use the isomorphism classes when talking about random graphs. As $n$ gets large, "most" graphs have no automorphisms, so their isomorphism classes have $n!$ elements, and the asymptotes of probabilities tend to agree with the much simpler model of random graphs.