Articles of random graphs

Probability that an undirected graph has cycles

If we know the probability $P$ that there exists an edge between two vertices of an undirected graph, let’s say $P= 1/v$, where $v$ is the number of vertices in the graph, what is the probability that the graph has cycles? I’ve twisted my brain with this. Can anyone help?

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was established that the bivariate mixed generating function of this class $\mathcal{G}$ of graphs on $n$ nodes and with $k$ edges […]

Indicator function for a vertex-induced random subgraph of $G$?

I am trying to find polynomial, indicator function or sometimes called structure function to express whether a vertex-induced random subgraph $H$ of $G$ is connected or not. The polynomial $\phi(G’)$ should be the undirected version while I am trying to figure out the direction version. So where I cannot fully understand the second line: it […]

What can be said about the number of connected components of $G(n,p)$ random graphs?

By a $G(n,p)$ graph we mean a graph on $n$ vertices, all possible edges are independently included randomly with probability $p$. What can be said about the number of connected components? For example, bounds or asymptotic behavior of the expected number of components as $n\rightarrow \infty$ or for $p$ close to 1.

What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

By a random $n\times n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$. I want to find the probability that such a graph contains an isolated vertex. Let $X$ and $Y$ be the vertex classes. I can calculate the […]

Expected number of triangles in a random graph of size $n$

Consider the set $V = \{1,2,\ldots,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random process: Each unordered pair $\{i,j\}$ of vertices, where $i \neq j$, occurs as an edge in $E$ with probability $p$, independently […]

Are the vertices of a Voronoi diagram obtained from a Sierpinski attractor also a kind of attractor?

Trying to understand how the Voronoi Diagrams work I did a test generating the Voronoi diagram of the points obtained from The Chaos Game algorithm when it is applied to a $3$-gon. The result is a set of points part of the Sierpinski attractor, the Voronoi cells and the vertices of each cell. This is […]

Probability spaces over graphs: which area has focus on them?

Suppose a simple graph $G$. Now consider probability space $G(v;p)$ where $0\leq p\leq 1$ and $v$ vertices. I want to calculate globally-determined properties of $G(v;p)$ such as connectivity and expected value of indicator function $$\mathbb E_{p\sim [0,1]^n}(\phi(G))$$ in terms of st-connectedness where $p$ follows let say uniform distribution. I want to understand which area investigates […]