An upper bound for the number of non-isomorphic graphs having exactly $m$ edges and no isolated vertices

Question

I asked this question in stackexchange a few days back (https://math.stackexchange.com/questions/2741806/bounding-the-number-of-non-isomorphic-graphs-having-m-edges-and-no-isolated-ve?noredirect=1#comment5658566_2741806), but did not get any satisfactory answer there. So I decided to ask it again in Mathoverflow.

Given a positive integer $m$, let $A_m$ denote the number of non-isomorphic graphs (connected or disconnected) having exactly $m$ edges and no isolated vertices. What is the tightest known bound on $A_m$?

More specifically, is it true that $A_m \leq m^{m^\alpha}$ for some $\alpha < 1$?

I would be glad if someone points out that this is not the case. Counterexamples of the form $A_m \geq m^m$ or $A_m \geq m!$ will also be highly valued by me!

Answer 1

Here is some information about the labelled case, based on E.A. Bender, E.R. Canfield and B.D. McKay, The asymptotic number of labeled graphs with n vertices, q edges, and no isolated vertices, J. Combinatorial Theory, Series A, 80 (1997) 124-150.

The number of labelled graphs with $m$ edges and no isolated vertices is $$ L_m = (1 + o(1))\, C_0\, (C_1 m)^m,$$ where $$C_0 =\frac{1}{2^{1+\frac14\ln 2}\ln 2}\approx 0.6397,\quad C_1 = \frac{2}{(\ln 2)^2e}\approx 1.5314.$$ Also, the distribution of the number of vertices in such a graph is asymptotically normal, with mean $$ n = \frac{m}{\ln 2}$$ and variance $O(m)$ (the precise value is given). It means that the bulk of these graphs have close to $m/\ln 2$ vertices.

I thought that the $L_m/n!$ would be a useful nonrigorous lower bound on the number of unlabelled graphs, but alas this quantity goes to 0. It means that most graphs in the class have very large automorphism groups. That is not a surprise given that the typical average degree is $2\ln(2)\approx 1.386$.

Answer 2

A lower bound $A_m\ge (\Omega(m))!$ can be obtained as follows. Let $n$ be a positive integer and $\pi$ an arbitrary permutation of $\{1,2,\dots,n\}$. Construct a graph $G(\pi)=(V,E(\pi))$ as follows.

Let $V=\{x_0, x_1, x_2, \dots, x_n\} \cup \{y_0,y_1, y_2, \dots, y_n\}$. Now add the following edges to $E(\pi)$:

1) all edges $x_0x_i$ and $y_0y_i$, $i=1,2,\dots,n$ (forming two copies of $K_{1,n}$)

2) all edges $x_ix_{i+1}$ and $y_iy_{i+1}$, $i=1,2,\dots,n-1$ (forming two copies of the path $P_n$)

3) all edges $x_iy_{\pi(i)}$, $i=1,2,\dots,n$ (forming a matching according to the permutation $\pi$).

The total number of edges is $5n$.

It is easy to see that $G(\pi)$ is isomorphic to at most seven other graphs $G(\pi')$ if $n\ge 5$. By adding a constant number of edges to distinguish $x_0$ from $y_0$, $x_1$ from $x_n$, and $y_1$ from $y_n$, the modified graphs $G'(\pi)$ would be pairwise non-isomorphic.