# Science Quiz / MTH 607 - Graph theory queestions

Random Science Quiz

## Can you name the MTH 607 - Graph theory queestions?

### Popular Quizzes Today

Challenge
Share
Tweet
Embed
Score
0/41
Timer
20:00
Quiz #1
A graph is _______ iff it contains no odd cycles
A tree with 25 vertex has _____ edges
A clique with 10 vertex has _____ edges
A graph homomorphism maps edges to ______
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
If G is a tree, then G is connected and has size
A graph is bipartite iff it contains no _____

### You're not logged in!

Compare scores with friends on all Sporcle quizzes.
OR

### Extras

Created Apr 16, 2010Source
Tags: