Open Daily: 10am - 10pm | Alley door pickup 10am - 7pm 3038 Hennepin Ave Minneapolis, MN
612-822-4611

  • Open Daily: 10am - 10pm
    Alley-side Pickup: 10am - 7pm

    3038 Hennepin Ave Minneapolis, MN
    612-822-4611

Open Daily: 10am - 10pm | Alley-side Pickup: 10am - 7pm
3038 Hennepin Ave Minneapolis, MN
612-822-4611
Extremal Problems in Digraphs.

Extremal Problems in Digraphs.

Sullivan, Blair D.

Paperback

General Mathematics

Currently unavailable to order

ISBN10: 124346271X
ISBN13: 9781243462718
Publisher: Proquest Umi Dissertation Pub
Pages: 104
Weight: 0.49
Height: 0.27 Width: 7.99 Depth: 10.00
Language: English
Let G be a finite simple directed graph on n vertices. Say G is m-free if it has no directed cycles of length at most m. In 1978, Caccetta and Haggkvist [3] conjectured that if G has minimum out-degree at least r, then G is not n/r -free. Finding upper bounds on the minimum out-degree in 3-free digraphs has been of particular interest in recent research. In this thesis, we present new results for several related problems in extremal directed graph theory. Let beta(G) denote the size of the smallest subset X ⊆ E(G) such that G\X has no directed cycles, and let g (G) be the number of non-edges of G. Fix an integer m >= 3; let G be m-free. For 3 0 so that all 3-free digraphs on n > 0 vertices have minimum out-degree at most cn.

Also in

General Mathematics

View All