Math 447 - Discrete Structures - Fall 2004

Professor:  Nancy Eaton
Office:  Tyler 222
phone:  874-4439 (O)

Office Hours:  Mon 12:30-2, Tues 11:30-1
E-mail:  eaton@math.uri.edu

Students who require accommodations and who have documentation from
Disability Services (874-2098) should make arrangements with me as soon as possible.

New Room - Washburn 208

Updated 12/12/04

• Text
• Supplemental material - check for downloads
• Course Content
• Syllabus
• Homework
• Specific assignments - check for updates – updated Oct 22!
• Project
• Exams
• Suggestions
• Your grade
• Review for exams

Text

We will use Introduction to Graph Theory by Chartrand and Zhang as a text for this course. I hope you find this to be a fine book with many examples, applications, and exercises.  Supplementary material will be used for those topics which are not covered in our text.

Supplemental Material

Some of the topics that are covered in this course are not in the text.  For those topics, some supplementary material will be used and you will be expected to take careful notes in class.  Downloads for all materials are listed here as they become available.   Even Cycles Euler Circuits Planar (Kuratowski and 5-color) Brooks and Vizings

Course Content

A combinatorial graph, or simply, graph, is a set of vertices V and edges E such that each edge consists of an unordered pairs of vertices. We can picture graphs using dots and curves.  For each vertex, draw a dot, anywhere you like.  Represent the edge {u, v} by drawing a curve from one vertex to the other.  For example, we draw the graph G=(V, E), where V={a, b, c, d, f, g} and E={{a, b}, {a, d}, {a, g}, {b, c}, {b, f}, {c, d}, {c, g}, {d, f}, {f, g}} below.

Notice that there is no vertex or dot in the center of the drawing.

Graph theory has many applications in Electrical Engineering and Computer Science. For example, the electrical engineer will be interested in planar graphs and the computer scientist in algorithms to properly color graphs. We will see some of these applications, but we must build up some background knowledge about graphs before we can make sense of such things as the thickness of a graph or the crossing number of a graph.

In the course of our study of Graph Theory, we will learn about the following topics as well: set theory, proof techniques, enumeration, and recursive formulas. There is no official prerequisite for this course however, it is recommended that you have been exposed to a variety of math and science courses. All topics will be treated in an introductory manner.

Specifically, we will cover the following topics:

Motivation:

Jobs and applicants

Scheduling

4-color map problem

Computer networks

Circuit board design

Background:

subgraphs 

walks, trails, paths, circuits, cycles

connected graph

digraphs

multigraphs 

common classes of graphs

matrix representation

Degrees - A party problem 

Isomorphic graphs - Algorithms

Coloring vertices - Scheduling

Trees - Counting labeled trees

Spanning trees - Minimum weight

Prefix codes 

Connectivity

Eulerian graphs

Hamiltonian graphs - The Traveling Salesman Problem

Planar graphs

Coloring planar graphs

Coloring edges of graphs

Matching

Factoring

Ramsey numbers

Domination

Network flows

Games Theory and Games on graphs

Syllabus

Date	Topic	Sec	Date	Topic	Sec
			Sep 9	Motivation	1.1
Sep 14	Background	1.2, 1.3	Sep 16	Background	1.4
Sep 21	Degrees	2.1, 2.2	Sep 23	Degrees	2.3, 2.4
Sep 28	Isomorphic graphs	3.1	Sep 30	Coloring vertices	10.2
Oct 5	Trees	4.1, 4.2	Oct 7	Spanning trees	4.3
Oct 12			Oct 14	Exam 1
Oct 19	Connectivity	5.1, 5.2	Oct 21	Connectivity	5.3
Oct 26	Eulerian graphs	6.1	Oct 28	Hamiltonian graphs	6.2
			Nov 4	Planar graphs	9.1
Nov 9	Coloring planar graphs Project proposal due	10.1	Nov 10(Wed)	Coloring edges	10.3
Nov 16	Matching	8.1	Nov 18	Factoring	8.2
Nov 23	Project due
Nov 30			Dec 2	Exam 2
Dec 7	Special topic		Dec 9	Extra Credit
			Dec 16	Final Exam

Homework

You learn by doing rather than by watching. Therefore, homework is very important.  You also learn by practice, so do as many of the examples assigned as possible. Homework will be assigned each time we begin to cover a new section in class. You should complete it by the next class period. I will ask you to hand in selected problems every week or so. You should provide careful explanations and be neat. When the exercise asks for a proof, give a formal proof.  We will practice this in class.  These problems will challenge your problem solving abilities. You may work in groups provided you follow the following guidelines. 

There are benefits to discussing the problems with your classmates.  If you become stuck on a problem, fresh ideas from someone else might provide you with some new angles to try.  In the academic community as well as in business and industry, people often work in teams.  So, it is good to get some practice working with others.  Working with someone from class will help you to improve your math communication skills as well.

I encourage you to work together under the following circumstances.

v Begin the problem on your own, do as much as you can.

v Ask someone from the class to explain the basic outline of a solution.

v If working with someone else, sometimes they will also ask you for your understanding of the basic outline.

v Take what you learned and write out the solution on your own, using your own words. 

v Never copy word for word from anyone else’s paper.  In fact it is better not to look at anyone else’s completed written solution or to show yours to anyone else.

v If you still do not completely understand the solution, you can ask your professor to look at what you wrote and try to clear up any parts of the solution that are not completely clear and accurate. 

The following is an excerpt from the University Manual.

8.27.11 A student's name on any written exercise (theme, report, notebook, paper, examination) shall be regarded as assurance that the work is the result of the student's own thought and study, stated in the student's own words and produced without assistance, except as quotation marks, references and footnotes acknowledge the use of other sources of assistance. Occasionally, students may be authorized to work jointly, but such effort must be indicated as joint on the work submitted.  Submitting the same paper for more than one course is considered a breach of academic integrity unless prior approval is given by the instructors.

Whenever you would like to discuss the class material, have any questions or are stuck on the homework, please visit me in my office either during my office hours or by appointment.

Specific Assignments

 Hints or solutions to the odd numbered problems are given in the back of the text.  Be sure to try the problem before looking at the solution.  Give it at least 15 minutes!

SECTION	HOMEWORK	HAND IN	Due date	Assn #
1.1	3, 4, 6, 7b, 8, 10	4, 6, 8, 10	Sep 14	1
1.2	11, 12, 15, 17	15, 17(b)	Sep 21	2
1.3	21, 22, 24, 25, 27	22, 24	Sep 21	2
1.4	30, 32(a,b)
2.1	1, 2, 3, 4, 5, 7, 9, 11, 14, 18	2(d), 4, 14, 18	Sep 28	3
2.2	19, 20, 21, 22, 23, 24, 26	19, 22, 26(b)	Oct 5	4
2.3	32, 34, 35	32	Oct 5	4
2.4	37, 38, 41	38	Oct 12	5
3.1	1, 2, 3, 4, 7, 8, 9, 10	8	Oct 12	5
10.2	1, 2, 3, 6, 10, 11, 12	6, 10	Oct 12	5
4.1	1, 2, 3, 5	2	Oct 19	6
4.2	7, 8, 9, 10, 13, 14, 16, 18, 21	8, 10, 18	Oct 19	6
4.3	25, 27, 28	28	Oct 26	7
5.1	1, 2, 3, 4, 5, 6	4, 6	Oct 26	7
5.2	9, 11, 12, 16	12, 16	Nov 9	8
5.3	18, 19, 21, 22, 24, 25, 27	18, 22(a), 24	Nov 9	8
6.1	1, 2, 4, 6	4	Nov 9	8
6.2	9, 10, 11, 12, 13, 14, 16	14, 16	Nov 16	9
9.1	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,	6, 14(a, b)	Nov 16	9
(9.1)	12, 14, 17, 19, 22	14(c), 22 – extra cred	Nov 18	A
10.1	(10.2) 4, 8, 9	4, 8	Nov 30	10
10.3	17, 18, 19, 20	18	Nov 30	10
(10.3)		20 – extra cred	Dec 9	B
8.1	1, 2, 3, 6, 7, 8, 11, 12, 13,	6(a)	Nov 30	10
(8.1)	14, 16	14	Dec 7	11
(8.1)		6(b), 16 – extra cred	Dec 9	B
8.2	17, 18, 19, 21, 24, 25, 27, 31, 32	32	Dec 7	11

Project

There is one project due on Nov 23 with a proposal due on Nov 9.  You are to select a research paper written about a topic in Graph theory from the list below that was published some time after 1999.  

Interval graphs

Perfect graphs

Clique covering number

List colorings of graphs

Crossing number

Thickness

Tree width

Rigidity

Visibility graphs

Graph labeling

Pebbling

Ramsey Theory - other than what is covered in section 11.1

Get a copy of the paper.  Read the paper, including the proofs.  Look up terms that you do not know from class or our book, using another source.  Write a report.  Your report should contain:

Section 1:

Title of the paper

Name(s) of the author(s)

Journal

Volume, section

Date

Pages

Section 2:

An explanation of the main result(s) in your words

Include definitions of terms that were not covered in our course.

Section 3:

A sketch of one of the proofs.  Be sure to say which result you are giving a proof of.

Your comments.

Section 4:

Attach a copy of the paper.

I suggest that you start this early and obtain several papers.  Skim reading them before choosing one for your report.  To obtain the papers, start with MathSciNet.  You can access this via the Math Dept. web page under "Web Resources".  Do a full search and enter 05C under "MSC Primary".  Find a paper in one of the following journals so that you can quickly obtain it either from the library or online, as long as you are using a URI computer. 

Discrete Applied Mathematics

Electronic Journal of Combinatorics

Journal of Graph Theory

Journal of Combinatorial Theory, Series B

Siam Journal of Discrete Mathematics

Discrete Math

Annals of Combinatorics

European Journal of Combinatorics

Journal of Discrete Algorithms

Exams

Tests will draw from material covered in class, that is, any theorems, proofs, example, or homework problem that we actually discuss in class is possible material for the tests. So, the best way to prepare for the tests will be to start with your class notes. Notice that implied in the last sentence is that you should take notes! There will be 2, 75-minute exams and a final. The hour exams will be given on Oct 14 and Dec 2 and the final will be on Dec 16.

Suggestions

1. Read the Book carefully. I chose this book because I believe it gives nice explanations of things. It may be helpful to read sections before we talk about them in class.
2. Do all of the homework assigned. You should spend an average of 6 hours a week on homework for this class. If you don't gain experience in doing the problems yourself, it will be hard to remember how to do them on a test. It is helpful to start study groups and work together on homework. I do believe that how well you do in this course will depend on how well you study.
3. Attend class to keep current, ask questions, and learn knew topics. Also, attending class allows you to see what is emphasized. Remember the material for the tests will come from what was emphasized.
4. Be sure to keep current of all topics. You will need to study a little almost everyday. If you don't understand something, don't let it wait too long because the concepts in this class build, one upon the next. You don't want the ``snowball effect'' to take over.
5. You may not understand an idea at first. Give it time to sink in. Sometimes you must go over it several times before it begins to make sense. It is not unusual for someone to be stuck on a particular kind of problem and not understand it in class. You may need to have it explained again, later. Please feel free to ask me to do so outside of class.
6. Note-cards - I suggest you buy a spiral bound set of note-cards.  You record simple statements, one per card, giving key definitions and theorems. Then you can use these as a flashcard type of studying method.

Review for Exams

Review for exam 1

Review for exam 2

Solution Key to Exam 1

Solution Key to Exam 2

Your Grade

Your grade will be based on your test scores, final exam score and homework grades. The scores are averaged and then weighted to compute your final grade according to the following percentages.

Homework	25%
Project	10%
2 tests	40%
Final	25%