Give a number of edges $|E|$, number of vertices $|V|$ and a $|V|\times 1$ vector of integers $T=[t_1, \cdots, t_{|V|}]$, I wish to construct an undirected graph with $|V|$ vertices, $|E|$ edges such that the first vertex $v_1$ participates in exactly $t_1$ triangles, the second vertex $v_2$ participates in exactly $t_2$ triangles and so on, to $v_{|V|}$ that should participate in exactly $t_{|V|}$ triangles. Given that I know that such graph exists, is there an algorithm to construct such graph?

  • $\begingroup$ Does the graph need to be randomly sampled? If so, and if |E| is reasonably small, I would try brute force: sample random graphs until I have one with the wanted property. If you already have a graph with the wanted properties, you may also try swapping groups of edges in a way that preserves them. Finally, if having a biased graph is ok, you may start with any graph and swap random pairs of edges in a way that gets you closer and closer to your goal (you then have to define a distance to the goal). These approaches are computationally costly, but they may work on small input cases. $\endgroup$ Commented Jul 18, 2020 at 6:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.