 Konigsberg Bridge |
 A Four Coloring of a Map |
Konigsberg Bridge |
A Four Coloring of a Map |
COURSE NUMBER: MATH 5340
TIME: 12:45-2:05 TR; PLACE: Online through Zoom CALL# 85243
INSTRUCTOR: Robert "Dr. Bob" Gardner; OFFICE: Room 308F of Gilbreath Hall
OFFICE HOURS: By appointment; PHONE: 439-6979 (Math Office 439-4349)
E-MAIL: gardnerr@etsu.edu
WEBPAGE: www.etsu.edu/math/gardner/gardner.htm.
TEXT: Graph Theory by J. A. Bondy and U. S. R. Murty, Graduate Texts in Mathematics 244 (Springer, 2008).
PREREQUISITE: The catalog states that "admission to the math graduate program or permission" are the formal prerequisite. Students must have some background in proving theorems and a working knowledge of linear algebra, but all graph theory definitions will be covered and we will start from first principals of graph theory.
DESIRE2LEARN: I will not rely on the Desire2Learn ("D2L") website. Instead, I will simply post all material directly on the internet. However, I will post your grades on D2L.
CLASS NOTES: We will use digital notes for the presentation of definitions, examples, and proofs of some theorems. Limited marginal notes, additional examples, and further explanations will be given using handwritten notes and a document camera. Copies of the notes are online. You should read the online notes to be covered in class before each class (we may not have class time to cover every little detail in the online notes). Try to understand the definitions, the examples, and the meanings of the theorems. After each class, you should read the section of the book covered in that class, paying particular attention to examples and proofs.
ABOUT THE COURSE: Graph theory is a relatively new area of math. It lies in the general area of "discrete math" (as opposed to continuous math, such as analysis and topology), along with design theory and coding theory. Historically, it is motivated by applied problems and still finds numerous applications, particularly in computer science (such as network design and the efficiency of algorithms). However, today it is a very vibrant area of pure mathematical research. ETSU has had a number of research graph theorists over the past several years, including Drs. Lawson, D. Knisley, Boland, Haynes, and Beeler. In this class we will survey graph theory, starting with first principles and definitions. So no background in graph theory is needed, but some background in proof techniques, matrix properties, and introductory modern algebra is assumed. Homework assignments will mostly involve the standard exercises in the text book, but will occasionally involve more advanced exercises. Some emphasis will be put on the research of those current ETSU faculty members involved in areas related to graph theory. In particular, some lectures will deal with graph (and digraph) decompositions, coverings, and packings. Automorphisms of graph (and digraph) decompositions will also be explored. We may have a few guest lectures given by my departmental colleagues on their area of research. A section of Graph Theory 2 (MATH 5450) will be offered in spring 2021, assuming there is an appropriate level of interest.
OUTLINE:
Our tentative outline is:
Chapter 1. Graphs: Vocabulary, neighborhoods, simple graph, finite graph, complete graph, bipartite graph, paths, cycles, incidence and adjacency matrices, regular graph, isomorphism, automorphism, Aut(G), hypergraph, projective plane, line graph, interval graph, connected components, Cartesian products, directed graphs, arcs, orinetation of a graph, tournament, Principle of Directional Duality, mixed graph, infinite graph, infinite path.
Chapter 2. Subgraphs: Edge and vertex deletion, embedding, maximal path, circumference, girth, acyclic graph, spanning subgraph, join of graphs, Hamilton path/cycle, symmetric difference, induced subgraph, weighted graph, Traveling Salesman Problem, identifying two vertices, edge contraction, graph decompositions/packings, coverings, digraph decompositions/packings/coverings, edge cut, even graph, bond, directed bonds, edge space, cycle space, bond space, hypomorphic graphs, graph reconstruction, the Reconstruction Conjecture, edge reconstruction, the Edge Reconstruction Conjecture, The Inclusion Exclusion Formula, The Mobius Inversion Formula, a sufficient condition for edge reconstuctibility.
Chapter 3. Connected Graphs: Walk, trail, distance, The Friendship (Graph) Theorem, cut edge and their classification, Konigsberg Bridge Problem, Euler graph, Fleury's Algorithm, connection in digraphs, cycle double covers, small cycle double cover, cycle double cover conjectures.
Chapter 4. Trees: Tree, forest, path connectedness of trees, leaf, rooted tree, branching, reachable vertices, median order, subtrees, spanning trees, classification of bipartite graphs, Cayley's Formula, number of spanning trees, cotree, fundamental cycle, even subgraphs, fundamental bonds, cyclomatic number.
Chapter 5. Nonseparable Graphs: Cut vertex, separation of a connected graph, nonseparable graph, block of a graph, ear of a graph, nested sequence of graphs, eat decomposition, directed ear, directed ear dcomposition, feedback arc set of a digraph, fundamental cycle of a digraph.
GRADING: Since this is an online class, your grade will be determined by the average on the assigned homework exercises. Grades will be assigned based on a 10 point scale with "plus" and "minus" grades being assigned on a 3 point subscale (for example, a 90, 91, 92 is an A-).
HOMEWORK: Homework will be assigned and collected at roughly one week intervals. YOU MUST SHOW ALL DETAILS ON THE HOMEWORK PROBLEMS!!! Justify every step and claim you make - this is how you convince me that you know what you are doing. You may find some answers online, but these rarely sufficiently justify all steps and are unacceptable as homework solutions.
ACADEMIC MISCONDUCT: While I suspect that you may work with each other on the homework problems, I expect that the work you turn in is your own and that you understand it. Some of the homework problems are fairly standard for this class, and you may find proofs online or in an online version of the solutions manual. The online proofs may not be done with the notation, definitions, and specific methods which we are developing and, therefore, are not acceptable for this class. If I get homework from two (or more) of you that is virtually identical, then neither of you will get any credit. If you copy homework solutions from an online source, then you will get no credit. These are examples of plagiarism and I will have to act on this as spelled out on ETSU's "Academic Integrity @ ETSU" webpage (last accessed 7/22/2020). To avoid this, do not copy homework and turn it in as your own!!! Even if you collaborate with someone, if you write the homework problems out in such a way that you understand all of the little steps and details, then it will be unique and your own work. If your homework is identical to one of your classmates, with the exception of using different symbols/variables and changing "hence" to "therefore," then we have a problem! If you copy a solution from a solution manual or from a website, then we have a problem! I will not hesitate to charge you with academic misconduct under these conditions.
SUPPLEMENTAL REFERENCES:
SYLLABUS ATTACHMENT: You can find an on-line version of the university's syllabus attachment (which contains general information concerning advisement, honor codes, dropping, etc.; last accessed 7/22/2020).
IMPORTANT DATES: (see the official ETSU calendar for more details; accessed 7/22/2020):
| |
|
||||
1.2. Isomorphisms and Automorphisms |
1.2.3 |
||||
1.2. Isomorphisms and Automorphisms |
1.2.9, 1.2.10(a1) |
||||
1.2. Isomorphisms and Automorphisms 1.3. Graphs Arising from Other Structures 1.4. Constructing Graphs from Other Graphs |
1.2.16(a,b,c) 1.3.3 1.4.3(a) |
||||
1.6. Infinite Graphs |
1.6.3 |
||||
2.3. Modifying Graphs |
2.3.1(a) |
||||
Return to Dr. Bob's webpage
Last updated: February 19, 2021.