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 LatapyJul 18, 2020 at 6:40
Add a comment
