Introductory and Algebraic Graph Theory

Math 510: Spring 2018
Thomas Zaslavsky

Course guide | Syllabus | Information & announcements | Meetings and Sessions

Assignments

Assignments: Diestel; Signed Graphs

Due Study/Read Recommended Required Notes
F 1/19: Up to p. 7 When you study, learn terminology and notation.
M 1/22: Through §1.3 Ch. 1 ## 1-3, 5
W 1/24: §1.4 Work on n0(Δ,D). (Not hand-in.) Quiz on the reading.
F 1/26: §1.5 Ch. 1 ## 6, 9, 11, 15. Quiz on the reading.
See the augmented Thm. 1.5.1.
M 1/29: §1.6 Prove Cor. 1.5.4. (I) Ch. 1 ## 8, 10, 12, 15. Quiz likely on the reading.
W 1/31: §1.7 Prove Prop. 1.4.1 with the book closed. Quiz ...
F 2/2: §1.7 Ch. 1 ## 16, 17, 22.   We'll discuss HW (I).
  On hand-in HW: No consulting any other sources. Looking up proofs instead of thinking is a no-no.
  Read about "Euler's Theorem" here.
M 2/5: §§1.8-10 (II) Ch. 1 ## 8, 20, 21, D1 (Iab, IIab, III, IV), D2.   Exer. 1.8: See here for explanation. Improve your previous answer if you can. If you're satisfied with the previous answer, you don't need to turn this in again.
W 2/7: — Snow day — Class to be made up later.
W 2/7 F 2/9: §§3.1-2 (see the syllabus) Ch. 1 ## 23, 27, 28, 33.
F 2/9 M 2/12: §3.3 Ch. 3 ## 1, 5. (III) Ch. 1 ## 29, 31, 32, 34; Ch. 3 # 6; D3.
W 2/14: §§4.1-2
F 2/16: §§4.1-3 (see the syllabus) D6. (IV) D4, D5 (a, b). Problem session 3:00-4:00 in WH-329.
M 2/19: §4.4   This is a major section. Kuratowski's Theorem is important itself, but even more, it leads to essential, fundamental questions and theorems.
W 2/21: §§4.5-6 (V) Ch. 3 ## 2, 8; Ch. 4 ## 3, 4, 13(a,b) (see grid); D7. Omit proofs.
  Ch. 4 # 13 is two problems: (a) the first sentence, (b) the remainder.
F 2/23: §5.1 Ch. 4 ## 8, 9, 25.   Do the recommended problems for discussion; don't hand them in. We'll discuss them in class today the problem session F 3/2.
M 2/26: §§5.2-3 (see the syllabus) (VI) Ch. 3 ## 3, 11, 15; Ch. 4 ## 22, 23, 32.
W 2/28: Edge coloring! König & Vizing.
F 3/2: — Snow day — Class to be made up later.
M 3/5: BREAK BREAK
W 3/7: BREAK BREAK
F 3/9: §6.1 (VII) Ch. 4 ## 17 (a, b), 20; Ch. 5 ## 7, 10 (a, b), 11, 17, 40. We finish proving Vizing; start flows.
Click for German letters.
Problem session
• 2:30-3:00 (Hilton Room) and
• 3:00-4:00 (WH-329).
• Prepare for discussion: Ch. 4 ## 8, 9, 25; Ch. 5 # 4.
M 3/12: §§6.2-4 (see the syllabus) §§1.9 & 6.3 represent one kind of algebraic graph theory.
W 3/14: §10.1 (see the syllabus) Also study Ore's Theorem (from class).
F 3/16: §§6.5-6 (see syllabus) Professor's day out. — Class to be made up later.
M 3/19
Tu 3/20: 		NPC §§1-2;
MTS §1		 Signed graphs! Papers for study: MTS and NPC (see the syllabus for compete citations).
Special lecture class Tues. 1:15 (WH-100E) due to aftereffects of math trip to Columbus.
W 3/21: — More basics of signed graphs. For today, know switching, sign of walk or cycle, balance.
NOTES! Take notes on signed graphs. The readings are only a small part of what you'll need to learn.
F 3/23: — (VIII) Ch. 5 ## 12, 16, 18, 20; Ch. 6 ## 6, 8, 10; Ch. 10 ## 2, 5; D8.
M 3/26: Announcements on signed graphs
W 3/28: MTS §§2, 4 # S2 for class discussion.
F 3/30: MIDTERM TEST ... SPRING BREAK ... (IX) ## S1, S3, S4(l, l0), S8. "S" problems are signed graph problems.
Course guide | Syllabus | Information & announcements | Meetings and Sessions

Assignments: Godsil & Royle

Due Study/*Read Recommended Required Notes
M 4/9: Ch. 1 Ch. 1 ## 1, 4, 11, 14. Much of the reading is familiar to you.
The problems are required because they'll help you start thinking about automorphisms. I'll ask for solution attempts in class.
W 4/11: §§2.1-2 Ch. 1 ## 5, 8, 15, 24. Again I'll ask for solution attempts in class.
F 4/13: — Professor's day out. Problem discussion (all students). Class to be made up later.
M 4/16: §§2.4-6, 3.1 Classes cancelled. —
W 4/18(1): §3.2 (X) Ch. 1 ## 8, 14, 15, 21; Ch. 2 ## 1, 2, 3, 11(→, ←), 12; G1, G2. See Lemma 2.5.1a.
W 4/18(2):
(3:30)		 *Read: §§3.3-4 §§3.3-4 will be familiar from Diestel. Keep an eye out for anything new.
F 4/20: §§4.1, 4.5
*Read: §3.7, §4.3, §4.4		 Check the syllabus about the readings.
"Read" means in particular you don't have to learn the proofs.
M 4/23: §§8.1-4 (XI) Ch. 2 # 16; Ch. 3 ## 2, 10, 13, 15; Ch. 4 # 1; G3 (a, b), G4. The reading should be review.
W 4/25(1): §§8.5-6 Some of the reading is review.
W 4/25(2):
(3:30)		 §§8.8-10, 8.12 See the syllabus for details.
F 4/27: §9.1; §§10.1-3 Catch up on reading. It now gets intensive.
You have to study Ch. 10 et seq. closely.
Suggested supplementary reading by S.S. Sane.
M 4/30: §§10.5, 11.1 (XII) Ch. 8 ## 9(a,b,c,d), 10, 24; G8v, G9, G10, G11, S10.
W 5/2(1):
(1:10)		 §§11.2-3 For a simplified outline of the connection between equiangular lines and graphs see this document.
W 5/2(2):
(3:30)		 §§11.5-6
F 5/4: Study §§12.1-3 & line graphs of s.g. (XIV) Ch. 10 ## 3, 4, 12(v=7); G12. The graph in #12 is J(n, 3, 1), where n is obvious (is it?).
I explain the example on pp. 250–251 in detail; see this document.
M 5/7: Study §§12.5-6 12.7-8
*Read §13.1		 G15. (XV) Ch. 11 ## 1(sw,!), 2(sw,iso), 3(eigs,reg); G13, G14. Highly recommended to do G15 for yourself.
Th 5/9: Problem/Discussion Session 1:00-5:00 in WH-100E
T 5/15: FINAL EXAM 12:50-2:50 in WH-100B
Course guide | Syllabus | Information & announcements | Meetings and Sessions