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

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.

-
Are the nodes labelled, or not? (That is, are we counting up to isomorphism, or not?) –  Graham Denham Jul 4 '11 at 19:54
Yes, the nodes are labelled. Sorry, I should have said this before. –  Rorsa Jul 5 '11 at 14:19
Also, suppose v,w,and u are vertices of a triangle in the graph. How are the triangle edges weighted in the definition of z_2? I can see the edges counted once each or twice each. Gerhard "Email Me About System Design" Paseman, 2011.07.05 –  Gerhard Paseman Jul 5 '11 at 21:20
If (v, w, u) is a triangle, the edge (w,u) is to be counted once in the set of "outgoing edges" of the node v. –  Rorsa Jul 6 '11 at 23:00

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.