0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are the nodes labelled, or not? (That is, are we counting up to isomorphism, or not?) $\endgroup$ Jul 4, 2011 at 19:54
  • $\begingroup$ Yes, the nodes are labelled. Sorry, I should have said this before. $\endgroup$
    – Rorsa
    Jul 5, 2011 at 14:19
  • $\begingroup$ 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 $\endgroup$ Jul 5, 2011 at 21:20
  • $\begingroup$ 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. $\endgroup$
    – Rorsa
    Jul 6, 2011 at 23:00

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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