If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of:

(A) a random graph (e.g., Erdos-Renyi graph),

(B) a small-world graph (e.g., Watts and Stragatz model) and

(C) a scale-free graph (e.g., Barabasi model)?

Assume I know the parameters related to the construction of the graphs (e.g., knowing the size of the graph, edge probability in ER graph, rewiring probability of small-world graph, the preferential attachment probability etc).

If any such results have been published somewhere, please point me to the right resources as well.


For Erdos Renyi, the degree distribution is binomial, see for example these Cornell lecture notes by John Hopcroft.


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.