2
$\begingroup$

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$.

For $d \in 2\mathbb{N} +1$ this trivially is impossible as no such graph exists: The number of incidences (connections between vertices and edges) is given by $|V|\cdot d = d^3 = 8k^3 + 12k^2 + 6k + 1$ (for some $k$). As the number of incidences is always double the number of edges $|E| = d^3/2$ is a contradiction.

This argument however, doesn't work for $d \in 2\mathbb{N}$.

My first guess was just constructing a random graph would do, however, this can get stuck in a local maximum. For instance in $d = 2$:

+---+    example for
|  /     an incomplete
| /      graph that
|/       cannot be
+   +    completed

A similar example can be constructed for $d = 4$ leaving up to two unconnectable vertices (essentially by using a 4-HyperCube).

I strongly suspect that for each $d$ the number of valid graphs significantly outweigh the number of incomplete graphs, but I would like to know how likely it is to end up with an incomplete graph. And if there is a better way to find these graphs than the random algorithm above (which could perhaps be fixed by breaking apart incomplete graphs, but that would not be guaranteed to terminate).

$\endgroup$
4
  • $\begingroup$ Do you mean degree or edge-degree? it seems from your post that you mean degree. If so such a graph is called a regular graph. Also there is a mistake when you insert d=2k+1, it should say $8k^3$ $\endgroup$ Jul 1, 2015 at 6:41
  • $\begingroup$ @MartinVatshelle: Yes, you're right, I meant regular graphs. Also fixed the 8. $\endgroup$
    – bitmask
    Jul 1, 2015 at 8:18
  • $\begingroup$ google.fr/… $\endgroup$
    – Lamine
    Jul 1, 2015 at 11:04
  • $\begingroup$ @Lamine, what is the point of the link? I see several research papers (as well as blog posts, etc), but no way to tell the most up-to-date or definitive answer to the question.... $\endgroup$
    – usul
    Jul 1, 2015 at 15:48

2 Answers 2

2
$\begingroup$

The standard simple way of generating random regular graphs is:

  • while the degree < d
    • choose a random perfect matching from the edges still possible to add to the graph
    • If no matching is possible, restart the process.

The problem with this is that the higher edge degree you want, the more likely it is for the algorithm to get stuck. I see many papers limiting themself to $|V|>d^3$, so I don't know if this process will work for you.

$\endgroup$
1
  • 1
    $\begingroup$ After thinking more about the problem I think I found a $n^2$-time and -space non-probabilistic algorithm that should work for all $d$ iff $|V|\cdot d$ is even and always terminates (even with an adversarial random number generator). I might post it after more scrutiny. $\endgroup$
    – bitmask
    Jul 1, 2015 at 16:11
0
$\begingroup$

Much progress was made recently in this area, see in particular this FOCS'19 paper:

Fast uniform generation of random graphs with given degree sequences
Andrii Arman, Pu Gao, Nicholas Wormald

and the more extensive arxiv version.

This paper presents an $O(nd+d^4)$ time algorithm for $d$-regular graphs when $d=o(\sqrt{n})$, and an implementation is provided.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .