An Erdös-Rényi random graph is a graph, which consists of N nodes and where each link between them is present with probability p. It comes natural then that the pdf giving the probability of a node in that gaph having k neighbours is a binomial.

The definition of a line graph is:

A line graph L(G) of a graph G is obtained by associating every link of G to a node of L(G) and connecting two nodes of L(G) iff the correspoding edges of G have a node.


If the degree distribution of an arbitrary E-R random graph G is binomial, as mentioned before, what would be the the degree distribution of its corresponding line graph L(G).


Fix an edge $e=\{u,w\}$ of $G$ and denote the vertex of $L(G)$ associated to it by $v_e$. By the definition of $L(G)$ should be clear that $$d_{L(G)}(v_e) = k \iff d_G(u)+d_G(w) = k+2$$ The reason for 2 at the right hand side of $d_G(u)+d_G(w) = k+2$ is that, if $e$ exists, then $u$ and $w$ already have degree at least one. But the connections which really contribute to the degree of $v_e$ are those made using other vertices but $u$ and $w$. Thus we have to subtract 1 from $d_G(u)$ and $d_G(w)$.

Consequently $ d_{L(G)}(v_e) \sim \text{bin}(2n-4,p)$


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.