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