It is known(Enumeration of graphs with a given and bounded degree sequence) that there is no a closed form formula for number of (labeled) graphs with bound on degree of vertices. Thus what I want to know is whether there is an asymptotic estimation of number of such unlabeled graphs like those here [Strauss&Ikeda].

For symmetric (unlabeled) graphs, we can reduce the problem of counting how many graphs(with certain properties) to certain form of group representation problem that can be solved using Polya's enumeration. However, if we put a bound on the degrees of vertices(or edges) of a graph $G$, usually we lose symmetries.

For graphs with such a bound on degrees of vertices, it is of importance in classification of Riemannian manifolds as well as physics since they can usually be realized as 1-skeleton of a class of manifolds (See: Can you determine whether a graph is the 1-skeleton of a polytope?) and it is known to connect with the $L(\epsilon)$ covering of small geodesic balls.

Thus each equivalence class of manifolds is chracterized by the abstract unlabelled graph $\Gamma_{\epsilon}$ defined by the 1-skeleton of the $L(\epsilon)$-covering. The order of any such graph(i.e. the number of vertices) is provided by the filling function $N_{(\epsilon)}$...[Mark J. Gotay et.al]pp.175-177(around it...do not have that book at hand)

Such results may also refine some statistical inference like the one here [Gao&Massam].

So I want to know the state-of-art in the direction of finding an asymptotic estimation/bound on the number of graphs with a bound on degrees of vertices. This post is different from Enumeration of graphs with a given and bounded degree sequence and the paper given there since we are dealing with unlabeled graphs in this post.


[Strauss&Ikeda]Strauss, David, and Michael Ikeda. "Pseudolikelihood estimation for social networks." Journal of the American Statistical Association 85.409 (1990): 204-212. http://hbanaszak.mjr.uw.edu.pl/TempTxt/PDF/Strauss_Ikeda_1990_PseudilikelihoodEstimationForSocialNetwor.pdf

[Mark J. Gotay et.al]Mathematical Aspects of Classical Field Theory,AMS 2010 http://www.ams.org/books/conm/132/conm132-endmatter.pdf

[Gao&Massam]Gao, Xin, and Hélène Massam. "Estimation of Symmetry-Constrained Gaussian Graphical Models: Application to Clustered Dense Networks." Journal of Computational and Graphical Statistics 24.4 (2015): 909-929.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.