In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the graph simplicity.
Consider two sequences of $n$ integers $a_i$ and $b_i$, for $i$ from $1$ to $n$, and build a (multi-)graph with vertices $1$ to $n$ using the following extension of the configuration model: attach to vertex $i$ exactly $a_i$ stubs, called edge stubs, and $2\cdot b_i$ stubs, called triangle stubs; then, take random pairs of edge stubs to form edges and random triplets of pairs of triangle stubs to form triangles.
I have several questions:
- what are the conditions on the two sequences that ensure that a simple graph (no loop, no multi-edge) can be obtained?
- is there a procedure to build such a simple graph, if it exists?
- how to compute the expected number of triangles in the graph? and the number of triangles involving each vertex?
- is there a procedure that builds such a graph with the additional constraint that vertex $i$ belongs to exactly $b_i$ triangles?
An extension of the Erdös-Gallai criterion would answer the first question. An extention of Havel-Hakimi algorithm would answer the two first questions.
For the two last questions, please note that some triangle may appear due to edge stub pairings, but also that triangle stubs "pairing" may lead to additional triangles, and combinations of edge and triangle stubs may also lead to additional triangles.
Are answers to these questions known in the literature?
This model was proposed in the paper Random graphs with clustering by M. E. J. Newman, but studied only within mean field approximation, if I am correct.
