-4
$\begingroup$

Is there currently an algorithm that given the number of vertices / nodes n, and the number of edges per node l, output all graph edges?

If not, is there an algorithm that can tell if such graph is possible?

In both cases, this is an undirected, loop-free graph.

$\endgroup$
5
  • 1
    $\begingroup$ Such a graph is not unique, not even up to isomorphism. Thus, it would be hard to find an algorithm to generate "the graph". Take for example two triangles and a circle on six points: In both graphs, you have six points and every point has degree two. $\endgroup$
    – Dirk
    Jun 29, 2017 at 10:20
  • 1
    $\begingroup$ Is it then possible to generate a graph with such properties? Just any graph. Thanks! $\endgroup$
    – DaKnOb
    Jun 29, 2017 at 10:21
  • 1
    $\begingroup$ Possible: Yes, this is a finite problem. However, I don't know of an algorithm to do it, so you either have to wait for someone else to come up with one or design one yourself. $\endgroup$
    – Dirk
    Jun 29, 2017 at 10:30
  • 1
    $\begingroup$ So far I've figured a way to make this work with a given l, but n must be restricted to (multiples of) 2^l. Thanks a lot of the help. Let's wait and see. $\endgroup$
    – DaKnOb
    Jun 29, 2017 at 10:36
  • $\begingroup$ Use a circulant graph: en.wikipedia.org/wiki/Circulant_graph which works for every $\ell,n$ such that $0\le\ell\le n-1$ and $\ell n$ is even. If $\ell n$ is odd, no graph exists. $\endgroup$ Jun 29, 2017 at 14:50

1 Answer 1

4
$\begingroup$

From the comments, you want every node to have the same weight. This is of course only possible if $n \geq \ell + 1$. Now assume we have such parameters. Pick $\ell+1$ vertices and form a complete graph on them. Continue, until you only have $k \leq \ell$ vertices left. Now there are two cases:

  1. $\ell - k$ is odd. Then form a complete graph on the remaining $k$ vertices, now every remaining is still missing $\ell - k-1$ edges, an even number. Remove an edge $(v,w)$ from the previous graphs and connect a remaining vertex to both $v$ and $w$, until everyone has the desired degree. You will have to remove $$\frac{k(\ell - k)}{2}$$ edges, which is possible, as each complete graph generated before contains $$\frac{\ell(\ell+1)}{2}$$ edges.
  2. $\ell - k$ is even. Then do not form the complete graph but rather connect every vertex directly to $\ell$ vertices by removing edges. Once again, there are enough edges to remove. This only works if $\ell$ is even, but we can assume $\ell$ even due to the handshaking lemma, which states that if $\ell$ and $n$ are both odd, then such a graph does not exist.
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.