A graph G is 5-regular and has 10 vertices. How many edges does the complement G' have

Quiz #2

R(3,3) =

R(2,25) =

R(3,4) =

R(T,Kn) = [This question was marked wrong on the quiz due to insufficient information]

The lower bound proved by Erdos on R(i,i) using the probalistic method is given by?

Quiz #3

A graph is 7 colourable iff it admits a homomorphism to?

In a museum with 25 walls, ___ many cameras are needed to guard it

A map can be coloured with at most __ colours

A graph with the property that x(H) = w(H) [chromatic number(H) = clique number(H)] for each induced subgraph H is called _____

If G with 7 vertex and G(complement) has 15 edges, then (chromatic number)x(G) is at most ___

Quiz #4

Expected # of edges of G(10,0.5) is ____

Szele's theorem says there's a torunament with n nodes and _____ many hamilton paths

Expected # of 4-cycles in G(6,0.5) is ____

Erdos proved that for every integer m >= 2, there's a graph G with 2 properties

Quiz #5

Expected degree of a vertex in G(25, 0.5) is _____

If X is random and E(X) = 10, then Pr(X>=2) = ________

t(n) = ______ is a threshold function for the appearance of triangles in G(n,p)

Chebyshev's inequality: If c > 0 is a real number and X is a random variable then: Pr (|X - E(X)| >= C)

Quiz #6

A graph of order t is power law if the number of nodes of degree is approximately _________

The small world property requires what 2 properties

In the ACL model with parameter p, the exponent of the power law is

Suppose you are in the 100th time-step of the preferential attachment model with parameter m = 1, and you are adding the new node v. The probability v is joined to the existing node u is given by _______

Quiz #7

The Perron-Frobenius theorem gives us what relation between the first and second eigenvalues (lambda)1, (lambda)2 of a primitive matrix _________ (Use the same lambda format in the answer)

For a random walk on the 7-cycle, the stationary distribution vector is _______

The row som of the adjecency matrix of a n-clique is _______

The rapid computation of the PageRank vector depends on which numerical method

Assuming the matrix P2 is defined, the formula for the Google matrix for a graph G or order n, with teleportation parameter c = 0.1 is _____ (this one was hard to put in sporcle so you may not get it right the first time)

Quiz #8

A graph is cop-win iff it's ________

State the relationship between the cop number c(G) and domination number y(G) of a graph G is: [Must have format: y(G) ___ c(G)]

Meyniel's conjecture states that for a connected graph G

State the cop number of the path with n vertices, Pn

State the domination number of the path with n vertices

Chapter 1

Sum of degrees is equal to _____ number of edges

In every grapn there is an ___ of ___ degree nodes