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$ Jul 18, 2020 at 6:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.