|
1
|
How many non-isomorphic classes of regular graphs on $(2n+1)^{m}$ vertices with $m(2n+1)^{m}$ edges with vertex degree $2m$, where $n,m \in \mathbb{N}$ are there? Is there a classification known? Can there can be more than one such class (that is are they all isomorphic)? Is there an example of such non-isomorphic graphs if there are any? |
|||||||||
|
|
6
|
The asymptotic number of $m$-regular graphs on $N$ vertices is well understood and can be found, for example, in Bollobas' Random Graphs (the argument uses Bollobas' "configuration model"). With probability $1$ a graph has no automorphisms, so this is also the number of isomorphism classes as long as $N$ is large. In your case $N=(2n+1)^m.$ So, for a reasonably sized $n$ (since yours is a natural number, $n>0$ should be fine), if you pick two random graphs, they will be non-isomorphic. |
|||||
|
|
1
|
For the connected case see http://oeis.org/A068934. For example, there are two non-isomorphic connected 3-regular graphs with 6 vertices.
|
|||||||||||||||||
|
