Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.