Register to reply

Directed graphs

by roadrunner
Tags: directed, graphs
Share this thread:
roadrunner
#1
Nov30-10, 08:21 PM
P: 103
Problem 4. Let k be an integer and let D be a directed graph with the property that
deg+(v) = k = deg-(v) for every v IN V (D). Prove that there exist vertex disjoint directed
cycles C1,...Ck so that SUm of V(Ci) = V (D). (HInt: construct a bipartite graph H from D
so that each vertex in D splits into two vertices in H.)

No idea how to even start...

Def: A transitive tournament is a tournament with no directed cycles. Equivalently, it is
a tournament so that the vertices can be ordered v1; v2,.....vn so that (vi, vj) is an edge
whenever i < j.

Problem 6. Let T be a tournament on n vertices. Prove that T contains a subgraph which is a transitive tournament on log2n + 1 vertices.

I have no idea how to do it, i made a ton of graphs with up to 8 vertices and found subgraphs that work, but can't find any way to prove this.


So confused
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts

Register to reply

Related Discussions
Converting Velocity-Time Graphs Into Acceleration Graphs Introductory Physics Homework 5
Good software for making directed graphs? Academic Guidance 3
Very simple calculus problem...graphs and velocity/time graphs to acceleration. Calculus & Beyond Homework 1
Directed sets Calculus & Beyond Homework 3
Equilibrium Points of Directed Graphs General Math 4