All Questions
Tagged with random-graphs degree-sequence
5 questions
3
votes
0
answers
107
views
Random graphs with prescibed degrees and triangles
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 ...
3
votes
1
answer
138
views
Degree sequences after vertex removals
Consider a graph $G=(V, E)$ with $|V|=n$ vertices. Let $(v_1, \dots, v_n)$ be an ordered list of its vertices. Let $G_i=G[\{v_{i+1}, \dots, v_n\}]$ be the induced subgraph on the last $n-i$ vertices. ...
2
votes
0
answers
69
views
Are two degree sequences compatible, for random simple graph generation?
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 ...
5
votes
3
answers
411
views
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
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 ...
10
votes
4
answers
528
views
When is a large graph with a given degree sequence likely to be connected?
Are there any results on whether a large random graph with a given degree distribution is likely to be connected?
In Erdős-Rényi graphs with $n$ vertices and $m$ edges, we have two sudden transitions ...