Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...