Graph Theory Syllabus

Professor Rosa Orellana

Office: 305 Bradley Hall Office Hours MWF 11:00-12:00 Thurs. 10-12 By Appointment

Phone: 646 - 2430 or BlitzMail:Rosa.C.Orellana@Dartmouth.EDU (preferred)

I encourage you to come to my office to discuss homework problems (yes, you can come before the homework is due), things that you don't understand in the course, opportunities for an REU (Research Experience for undergraduates) or if you are wondering what course to take next and need a little guidance.

This course will focus on Chapters 1-7 as well as additional topics pertaining to class. Fundamental concepts of graphs and digraphs, trees, matchings, factorizations, connectivity, networks, graph colorings, planar graphs, and eulerian and hamiltonian graphs will be studied. Famous problems in Graph Theory include: Minimum Connector Problem (building roads at minimum cost), the Marriage Problem (matching men and women into compatible pairs), the Assignment Problem (filling n jobs in the best way), the Network Flow Problem (maximizing flow in a network), the Committee Scheduling Problem (using the fewest time slots), the Four Color Problem (coloring maps with four colors so that adjacent regions have different colors), and the Traveling Salesman Problem (visiting n cities with minimum cost).

Required

• Introduction to Graph Theory by D. West

• There will be two types of homework assigned in this course. Both will be assigned daily. The first type (3-5 problems) will be computational in nature and it will be due at the begining of every lecture. The second type will consist of some proofs and this will be assigned weekly (about 5 problems). Written homework will be due at the beginning of class.
• All homework assignments will be posted on the course assignment's web page.
• Late homework will not be accepted under any circumstance. Since this seems harsh, I will allow you to drop 2 homeworks with lowest scores from each type.
• Unexcused late and missing papers count zero. Please keep all your papers for records. It is your responsibility to pick up your homework.
• Homework is to be written neatly using 8 1/2 x 11 inch paper. Do not use paper from a spiral notebook unless you can tear off the ragged edge. All papers are to be stapled.
• Use English. If you can't read your solutions aloud as fluently as if you were reading your textbook, try using nouns and verbs in your write ups! Make sure that computations are explained.

If you do not follow these guidelines, your homework will be returned to you ungraded.

There is a project for this class. Click here to find out more about it.

There will be two in-class exams and a final examination. They will probably be held at the begining of the fourth and at the begining of the eighth week. The exact dates will be announced during class at least one week before the exam.

The Registrar's Office schedules the final exam, which will occur during the period June 1 through June 5. If you must make travel plans before the schedule for final exams appears, do not make plans to leave Hanover before June 5th. Exams will not be given early to accommodate travel plans under any circumstances.

Class participation will count 5% towards your grade. This means attending class and office hours as well as asking and responding to questions

"Mathematics is not for spectators; in order to gain in understanding, confidence, and enthusiasm one has to participate." M.A. Armstrong

On Exams: No help given or received from anyone. You may not use books or notes during in-class exams.

On Homework: Collaboration is permitted and encouraged, but NO COPYING . In other words, you should feel free to talk to other students while you are in the process of thinking about a problem. However, when it comes time to write up your solutions, you should do this by yourself without outside assistance.

Students with disabilities who will be taking this course and may need disability-related classroom accommodations are encouraged to make an appointment to see their instructor as soon as possible, certainly within the first two weeks of the course. Also, they should stop by the Academic Skills Center in Collis Center to register for support services.