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$
$\endgroup$
1
-
$\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$– Matthieu LatapyCommented Jul 18, 2020 at 6:40
Add a comment
|