0
$\begingroup$

Question:

given a vertex $v$ of a symmetric random graph $G$ without self loops and parallel edges, what is the expected number edges in the subgraph induced by the vertices $u\in G\setminus v:\ (u,v)\in G$?

The model of the random graph is intentionally left open, but the Erdös-Renyi may be assumed.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Well, in $G(n,p)$, any such edge is included with probability $p^3$, hence the expected number is $p^3\binom{n-1}2$. Or am I missing something? $\endgroup$
    – Emil Jeřábek
    Commented Jan 24 at 18:25
  • $\begingroup$ In $G(n,M)$, I get $\frac{M(M-1)(M-2)}{\binom n2\left(\binom n2-1\right)\left(\binom n2-2\right)}\binom{n-1}2$. $\endgroup$
    – Emil Jeřábek
    Commented Jan 24 at 18:31

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .