Professor: Ron Gould
Text: Graph Theory by Ron Gould supplied off the web with
additional materials provided.
| Office: 432 Mathematics and Science Center
| Office Hours: 2:00-3:00PM WF - or by appointment
|
| Office Phone: 404-727-7924
| email: rg@mathcs.emory.edu
|
|
Some Important Graphs:
Petersen Graph
Turan Graph
Tutte Graph
Reading Assignments:
Materials: Copyright 2001 - Ronald J. Gould
This material is intended for use by students in Math 532 only, or with the permission of the author.
- Table of Contents
[ps]
[pdf]
- Chapter Seven - Matchings and r-Factors
[ps] [pdf]
- Chapter Eight - Independence
[ps] [pdf]
- Chapter Ten - Extremal Theory
[ps]
[pdf]
- Appendix
[ps]
[pdf]
- Index
[ps]
[pdf]
- Vizing's Theorem Proof
[pdf]
Graph Theory Hall of Fame: (semester 2)
Erdos
Tutte
Turan
Written Assignments:
- Handout Chapter - problems: Page 125: 33, 34, 36
Page 141: Problem 42 and Page 150-151: Problems 45, 46, 55.
Also
Problem: Find an embedding for:
(i) K(4,4) on the torus, (ii) K(4,5) on the double torus,
(iii) K(6) on the torus, (iv) K(8) on the double torus.
Chapter 7 - problems 1, 2, 3, 4, 5, 6, 12, 18, 19, 29.
Chapter 8 - problems 1, 4, 5, 7, 11, 16, 26c, 27 and 28.
Also, show the Petersen graph has a nowhere zero 5-flow.
Chapter 10 - problems 1, 2, 3, 4, 18, 19.
Also, determine which of the following functions is convex. Consider the interval as ( 1, inf ).
a. f(x) = sqrt(x)
b. f(x) = x choose 2, (i.e. binomial coefficients)
c. f(x) = x ^ 2 (i.e. x squared)
d. f(x) = log x
e. Let X(G) be the number of edges of G not in triangles. Find E(X) in model A and in Model B.
Do almost all graphs have the property that every edge is in a triangle?
Tournament problems:
From handouts, page 148 problems 10, 11, 12 and from page 11 problems 3 and 4.