Search Results

The implementation by Nick Wormald and colleagues is available from his webpage.

The paper below presents a linear-time algorithm for uniform generation of random graphs with given degree sequences [1]. This is very interesting in practice, but I found no implementation. However, …

The question you ask is, in my opinion, extremely important: decomposing a graph into a (small) set of small graphs (the tiles or ego-centered sub-graphs, for instance), and then characterizing how th …

Several works study the degree sequence obtained when vertices are removed from random graphs with given degree sequence. Vertices are generally removed by decreasing order of degrees, or uniformly at …

Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence. …

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 gr …

Question. Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence us …

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no lo …

This is a much studied question, at the crossroad of several fields: epidemiology, mathematics, statistical mechanics, and computer science, at least. The model you consider is known as SI with parame …

This is really not an answer to your question, but too long for a comment and I think it may be of interest. I would like to relate your question to community detection in graphs. There is a wide vari …

I fear the question is difficult in its general form: the answer will strongly depends on the assumptions we make regarding the initial graph, and on how we choose $n$. As noticed by @dodd, in particu …

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no lo …

The answer to this question is No. Let us assume $V = \{1,2,3,4,5,6\}$ and consider degree sequences $a = [3,2,2,1,0,0]$, $b = [1,0,0,3,2,2]$ and $c = a+b = [4,2,2,4,2,2]$. The only simple graph with …