Register to reply

Directed graphs

by roadrunner
Tags: directed, graphs
Share this thread:
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, 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
'Office life' of bacteria may be their weak spot
Lunar explorers will walk at higher speeds than thought
Philips introduces BlueTouch, PulseRelief control for pain relief

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