 Konigsberg Bridge |
 A Four Coloring of a Map |
Konigsberg Bridge |
A Four Coloring of a Map |
COURSE NUMBER: MATH 5340
TIME: 1:20-2:40 TR; PLACE: Gilbreath Hall 104 CALL# 84731
INSTRUCTOR: Robert "Dr. Bob" Gardner; OFFICE: Room 308F of Gilbreath Hall
OFFICE HOURS: 4:15-5:00 TR in Gilbreath 104 (as needed); PHONE: 439-6979 (Math Office 439-4349)
E-MAIL: gardnerr@etsu.edu
WEBPAGE: Dr. Bob's faculty webpage.
TEXT: Graph Theory by J. A. Bondy and U. S. R. Murty, Graduate Texts in Mathematics 244 (Springer, 2008). We will also use (as a supplemental source) Algebraic Graph Theory by Chris Godsil and Gordon Royle, Graduate Texts in Mathematics 207 (Springer, 2001).
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 and group theory, but all graph theory definitions will be covered and we will start from first principals of graph theory.
DESIRE2LEARN: I will not rely much on the Desire2Learn ("D2L") website. Instead, I will simply post all material directly on the internet. However, I will post your grades and homework solutions 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 on the whiteboard or through the document camera. Copies of the notes for the material from Bondy and Murty are online. Copies of the notes for the supplemental material from Godsil and Royle are also online. You should read the online notes to be covered in class before each class and try to at least understand the definitions, examples, and the meanings of the theorems.
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 (and, part-time, Godbole, Gardner, and Keaton). 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 2025, assuming there is an appropriate level of interest.
OUTLINE:
Our tentative outline is (we may bounce around some through the algebraic graph theory material):
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, orientation of a graph, tournament, Principle of Directional Duality, mixed graph, infinite graph, infinite path.
Chapter 1 on Algebraic Graph Theory. Graphs: Induced subgraph, clique, independent set, tree/forest, automorphism group, symmetric group, distance, homomorphisms, proper colouring, retraction, circulant graph, the graph J(v,k,i) and its automorphism group, Johnson graphs, Kneser graphs, line graphs and some classifications, congruence of graphs/line graphs, planar graph, plane embedding, plane graph, face of an embedding, Euler's Formula, embeddings on surfaces.
Chapter 2 on Algebraic Graph Theory. Groups: Permutation groups, symmetric groups, transitive permutation, group action, stabilizers and cosets, conjugation and conjugacy class, Burnside's Formula (Lemma 2.2.4), asymmetric graph, isomorphism class, asymmetric graphs, "almost all graphs are asymmetric," orbitals of transitive permutation group, rank of a group, classification of symmetric orbitals in terms of permutations, primitivity, connectivity.
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 on Algebraic Graph Theory. Transitive Graphs: Cayley graph, Cayley digraph, Cayley graphs are vertex
transitive, Edge transitive graph, arc transitive digraph, Semiregular and regular permutation group, group automorphisms and their relationship to isomorphic Cayley graphs, Cayley graphs and Hamilton cycles, transpositions and minimal generating sets of a group.
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, ear decomposition, directed ear, directed ear decomposition, feedback arc set of a digraph, fundamental cycle of a digraph.
GRADING: Homework to be turned in will be assigned regularly. You grade will be based on your performance on the homework. Grades will be assigned based on a 10 point scale with "plus" and "minus" grades being assigned as appropriate. Based on the assignment of grad points by ETSU, the plus and minus grades should be given on a 3 point subscale. For example, a B+ corresponds to an average of 87, 88, or 89; an A- corresponds to an average of 90, 91, or 92; an A corresponds to an average of 93 to 100 (ETSU does not grant A+ grades and the highest passing grade in a graduate class is C), etc.
HOMEWORK: Homework will be assigned and collected at one week intervals. It will normally be due on Saturdays at midnight and you will be expected to submit scans in PDF of your work to D2L. 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: 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 proofs generated by a Generative Artificial Intelligence (such as mathgpt). The online proofs or AI generated 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 8/18/2024). To avoid this, do not copy homework and turn it in as your own!!! 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, a website, or use AI, then we have a problem! I will not hesitate to charge you with academic misconduct under these conditions.
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 8/18/2024).
SUPPLEMENTAL REFERENCES:
IMPORTANT DATES: (see the official ETSU calendar for more details; accessed 8/18/2024):
| |
|
|||
2.5. Edge Cuts and Bonds |
2.5.1(a), 2.5.1(b) |
|||
2.6. Even Subgraphs |
2.6.4(a), 2.6.4(b) |
|||
3.3. Euler Tours |
3.3.1, 3.3.4(a) |
|||
4.2. Spanning Trees 4.3. Fundamental Cycles and Bonds |
4.2.1(a), 4.3.6a(i) |
|||
Return to Dr. Bob's webpage
Last updated: December 4, 2024.