# Questions tagged [random-graphs]

A random graph is a graph - a set of vertices and edges - 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$. Use (graphing-functions) instead if your question is about graphing or plotting functions.

886 questions
Filter by
Sorted by
Tagged with
24 views

### Confusion regarding small-O notation in a graph theory paper

Let $G$ be an $n$-vertex $d$-regular graph, where $d = n^{0.25}$. Choosing $s$ to be a constant, consider the quantity $$((n - d)d - s)^2.$$ Expanding this out, we can ...
1 vote
29 views

### Expected depth of random tree which randomly select the parent node for every node.

Consider using the following method to generate a tree: Set node $1$ as the root; For node $i$ ($i \in [2,n]$), randomly select the parent node in $[1,i)$. (The expression of the interval here is ...
• 19
29 views

### Writing the equation that makes the meta log [closed]

How to write the equation that will make me the meta logo ? An equation, if I put it in desmos or GeoGebra, it will make me the meta logo (the same company of facebook) ?
123 views

### Number of choices of edges in a regular graph

Let $G = (V, E)$ be an $n$ vertex $d$ regular graph and let $\epsilon$ and $\epsilon'$ be a subset of edges such that $$\epsilon \subseteq E,~~\epsilon' \not\subset E.$$ Let $(u, w) \in \epsilon$. ...
52 views

### Expected number of edges required for a graph to have a triangle.

I am considering graphs on $n$ with edges added iid randomly with probability $p$. I have come across this post for the expected number of edges for a graph to have a triangle. In the question, they ...
1 vote
59 views

### Watts-Strogatz model: no edge from $p = 0$ graph should exist in $p = 1$ graph?

I'm trying to implement the Watts-Strogatz model for small-world networks. My understanding is that the procedure is as follows: 1. Start with a Regular Graph: Begin by creating a ring lattice where ...
• 4,300