Introduction to Random Graphs Flashcards
1
Q
graph
A
pair of vertex set and edge set
2
Q
complete graph
A
n vertices and all possible edges
3
Q
subgraph
A
subset of vertices and subset of edges
4
Q
G(n,p) Erdos-Renyi random graph
A
random spanning subgraph of Kn
P(E(G(n,p))=s)=p^s(1-p)^{{n choose 2} - s}
5
Q
connected
A
there is a path between any pair of vertices
//one component
6
Q
cycle
A
sequence of distinct vertices and there is edge v_n to v_1
7
Q
occurs with high probability
A
lim P(A_n) =1 as n tends to infinity
8
Q
neighbour
A
(v,w) in E
9
Q
edges in complete
A
n choose 2
10
Q
spanning subgraph
A
V’=V
11
Q
tree
A
connected graph with no cycles
12
Q
component
A
maximal connected subgraph
13
Q
Cayley’s formula/number of trees on n vertices
A
n^{n-2}
14
Q
a_n=o(b_n)
A
a_n/b_n tends to 0 as n tends to infinity
15
Q
a_n=O(b_n)
A
there exists C such that a_n =< Cb_n for all n
