Difference between revisions of "Math 355: Graph Theory"
m (moved Math 355 to Math 355: Graph Theory) |
(→Minimal learning outcomes) |
||
| Line 23: | Line 23: | ||
=== Minimal learning outcomes === | === Minimal learning outcomes === | ||
| − | + | Definition of a graph, examples (trees, paths, cycles, Petersen graph, etc.), First Theorem of Graph Theory, isomorphisms of graphs and graph invariants, chromatic number, connectivity, planar graphs and conditions for planarity, statements of Four Color Theorem and Kuratowski's theorem, Hamiltonian cycles, spectral graph theory (networking, expanders, Ramanujan graphs). | |
| + | |||
| + | Additional topics from 1) proof of Kuratowski's theorem, 2) definition of the Euler characteristic and proof of Euler's characteristic formula for the genus, 3) proof of the Chvatal-Erdos theorem on the existence of Hamiltonian cycles, 4) characterization of Ramanujan graphs by the Riemann hypothesis of its zeta function. | ||
| + | |||
<div style="-moz-column-count:2; column-count:2;"> | <div style="-moz-column-count:2; column-count:2;"> | ||
Revision as of 11:28, 9 November 2017
Contents
Catalog Information
Title
Graph Theory.
(Credit Hours:Lecture Hours:Lab Hours)
(3:3:0)
Offered
W
Prerequisite
Description
Maps, graphs and digraphs, coloring problems, applications.
Desired Learning Outcomes
Prerequisites
Math 313.
Minimal learning outcomes
Definition of a graph, examples (trees, paths, cycles, Petersen graph, etc.), First Theorem of Graph Theory, isomorphisms of graphs and graph invariants, chromatic number, connectivity, planar graphs and conditions for planarity, statements of Four Color Theorem and Kuratowski's theorem, Hamiltonian cycles, spectral graph theory (networking, expanders, Ramanujan graphs).
Additional topics from 1) proof of Kuratowski's theorem, 2) definition of the Euler characteristic and proof of Euler's characteristic formula for the genus, 3) proof of the Chvatal-Erdos theorem on the existence of Hamiltonian cycles, 4) characterization of Ramanujan graphs by the Riemann hypothesis of its zeta function.
Textbooks
Possible textbooks for this course include (but are not limited to):
- Graph Theory by Rusell Merris
- Applied Combinatorics by Alan Tucker (Chapters 1-4 on Graph Theory).
A good additional resource is An Introduction to Graph Theory by Douglas B. West, but the book is probably too encyclopedic to use as a main text.
Additional topics
Possible other topics include spectral theory of graphs.
