Given a collection of n rooted trees with depth h, we give a necessary and sufficient condition for this collection to be the collection of h-depth universal covering neighborhoods at each vertex.
For @math , the number of labeled graphs with a given degree sequence is asymptotically known in many asymptotic regimes, see notably @cite_6 , [Theorem 2.16] MR1864966 and references therein. For general @math , this question has been recently adressed in @cite_2 in the regime where the maximal degree is uniformly bounded. The motivation came from the Benjamini-Schramm topology of rooted graphs.
@cite_6 @cite_2
2004542856 2039990322
We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d1,…,dn). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0-1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 It is shown that almost all labelled r -regular graphs are r -connected, for any fixed r ≥3. This is an instance of a more general result which applies to labelled locally restricted graphs whose points have degrees lying between r and R , where r and R are fixed, 3≤ r ≤ R . The proof employs a known asymptotic formula for the numbers of these locally restricted graphs. It is also demonstrated that for fixed k >0 and r ≥3, almost all labelled r -regular graphs with girth at least [ k ( r −2)] are cyclically k -connected. This provides an asymptotic formula for the number of labelled cyclically k -connected r -regular graphs with p points, for fixed k and r .