How many graphs with given average degree and average number of outgoing nodes?

Question

Hi, does anyone know if it is known what is the number of undirected graphs with the following properties:

• Number of nodes: $N$, a big number,
• Average degree: $z_1$,
• Average number of outgoing edges $z_2$, where an outgoing edges are all edges leaving one of your neighbors (except the one that connects you to that neighbor).

?

I interested in asymptotic results for large N.

Similarly, the entropy of an ensemble of graphs such that the average degree is $z_1$ and the average number of outgoing edges is $z_2$ is also of interest.

EDIT: The definition of $z_2$ is here: http://www.santafe.edu/media/workingpapers/00-07-042.pdf on section F, "Numbers of neighbors and average path length". Sorry for the loose definition. $z_2$ is also the number of second neighbors.

Thanks.

Answer 1

I do not understand what your outgoing edges are but the number of undirected graphs with $N$ labeled vertices and average degree $d$ (which you call $z_1$ but $d$ seems more natural to me) is approximatively given by $${2^{N(N-1)/2}\choose dN/2}$$ since this is the number of all possible adjacency matrices.

The asymptotics for fixed $d$ and $N\rightarrow\infty$ are then given by $$2^{dN^2(N-1)/4}\frac{1}{(dN/2)!}$$ which can be made more explicit using Stirling's formula.