# Tagged Questions

A random graph is a graph that is chosen according to some probability distribution. In the most common model, $G_{n, p}$, a graph has $n$ vertices, and edges are present independently with probability $p$.

50 views

### Elementary proof for average number of tree components in a random forest of fixed size

In Flajolet's & Sedgewick's "Analytic Combinatorics" I found the statement that for a forest ("Catalan", i.e. collection of ordered trees) of size $n$, uniformly distributed, the number of tree ...
69 views

### Sequence of Erdos-Renyi random graphs convergent with probability 1

Definitions Let $H,G$ be finite simple graphs. Then the density of $H$ in $G$, denoted $d(H,G)$, is defined as the probability that a randomly chosen $|H|$-tuple of vertices of $G$ induce a graph ...
22 views

### 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')$ ...
29 views

### Which Random Graph model on Reliability network when vertices deleted?

The reliability network when edges deleted corresponds to binomial random graph model that is also called Bernoulli Model. The page 3 of Random Graphs book (2000) by Svante Janson, Tomasz Luczak and ...
12 views

### Eulerian Cycle in a Random Bipartite Graph

I want to know (or possibly a pointer to a relevant text) the probability of having an Eulerian cycle in a random bipartite graph. I assume an Erdos-Renyi model $G(n,m,p)$, where the number of nodes ...
32 views

29 views

### Probability of G(4, 1/2) random graph being connected

Suppose we have a random undirected graph G(4, 1/2), i.e. the probability of any two of the four total vertices being connected is 1/2. how to find the probability that Probability (G(4, 1/2) is ...
19 views

### Creating Barabási–Albert(BA) graph with spacific node and edgs

I am trying to construct a BA graph with 500 nodes and about 37000 edges. The number of edges to attach from a new node to existing nodes should be at least 91 to make enough number of edges. I ...
67 views

49 views

23 views

### Random Geometric Graph in unit disk

According to the Wikipedia article, to define a random geometric graph, one needs a metric space. In the examples they give for 2D random geometric graphs, they say that "an RGG can be constructed ...
69 views

48 views

### Probability of at least one isolated clique forming

Is there any "famous" random graph model in which the probability of at least one isolated clique forming is monotonic in the parameters? For instance, are any results known in this matter for the ...
39 views

27 views

### The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
28 views

### Probability of maximum degree in On random graphs I by Erdos

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and ...
I am going through The Maximum Degree of a Random Graph by RIORDAN et al. On the second page, the notation $\mathbb{P}(\mathcal{D})$ is used which I assume the power set of the set $\mathcal{D}$. ...
### The random graph quantity $S(n: K, L)$
I am going through Degree sequences of random graphs by Béla Bollobás. On page $3$ the author introduces the quantity $S(n: K, L)$ without any explanation. Could anyone please help me in ...