MTH 607 - Graph theory queestions

Random Science Quiz

Can you name the MTH 607 - Graph theory queestions?

Quiz not verified by Sporcle

How to Play
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.
Sign Up with Email
Log In

You Might Also Like...

Show Comments


Your Account Isn't Verified!

In order to create a playlist on Sporcle, you need to verify the email address you used during registration. Go to your Sporcle Settings to finish the process.