MATH 613-600. Graph Theory

Fall, 2011, MWF 11:30- 12:20p.m., BLOC 160

    Instructor: Dr. Catherine Yan

    Office: Milner 220

    E-mail: cyan@math.tamu.edu,

    Class: MWF 11:30--12:20, BLOC 160

    Office hours: Wednesday, 10:00a.m.--11 a.m.

    Level : Graduate

    Prerequisites : Math 302 (Discrete Mathematics), or Math 431 (Structures and methods in Combinatorics), or equivalent will be sufficient.

    Course Description : This is a course at the beginning graduate level to help the students gain basic knowledge of the structure of graphs and the techniques used to analyze problems in graph theory and discrete structures.

    The course will cover fundamental concepts such as graphs, cycle, path, circuit, trees, matchings and factors, connectivuties and coloring, network. We will also introduce topics in currently active research areas, including Ramsey theory, extremal combinatorics, algebraic graph theory, combinatorial optimation, and probabistic methods. Time allows, we will also give an introduction to matroids.

    Textbook.

    Introduction to Graph theory, by Douglas West, second edition, Prentice Hall, 2001.

    Also a main reference: A Counrse in Combinatorics, by J.H. van Lint and R.M. Wilson, 2nd edition, Cambridge University Press.

    Grading: Homework assignments will be given bi-weekly. As exercise is an important part of combinatorics, anyone who doesn't hand in homework fails the course automatically. No late home work will be accepted except for university-approved excuses.

    The grade will be determined by your homework (70%) and a final project (30%).

    Announcement:
    There is no class on October 21.     Instead, you are encouraged to attend the Algebra and Combinatorics Seminar, 3--3:50pm, Milner 317. Dr. E. Yi will talk on On Chromatic Number, Domination Number, and Metric Dimension of Functigraphs
    There is no class on Novermber 23.

    First-day Handout

    Homework Assignment

    Homework 1 Assign on Sep 2. Due on Sep 16, in class.

    Homework 2 Assign on Sep 16. Due on Sep 30, in class.

    Homework 3 Assign on Sep 30. Due on Oct 14, in class.

    Homework 4 Assign on Oct 14. Due on Oct 28, in class.

    Homework 5 Assign on Oct 28. Due on Nov 18, in class.

    Homework 6 Assign on Nov. 18. Due on Dec 5, in class. It can be extended to Dec. 12, 3pm.

    Description of Project

    See the pdf file here, posted by October 15. The report is due on Dec 2, 2011.

    List of Papers for the projects

    This is the list of papers that some students have chosen to work on their projects.

    1. R. Ahuja, et.al. SOLVING THE CONVEX COST INTEGER DUAL NETWORK FLOW PROBLEM.
    2. J. A. Bondy and F. Mercier, Switching Reconstruction of Digraphs, Journal of Graph theory.
    3. A. Busch, M. Jacobson and R. Raid, On arc-traceable tournaments
    4. Tomasz Bartnicki, Jarosław Grytczuk, H. A. Kierstead, and Xuding Zhu, "The Map-Coloring Game",
    5. Dankelmann, Erwin, Mukwembi, Rodrigues, Mwambene, and Sabidussi Automorphism Group and Diameter of a Graph,
    6. M. Ferrara, M. Jacobson and A. Harris, Cycle lengths in Hamiltonian grphas with a pair of vertices having large degree sum.
    7. Hou, Wu, Liu, and Liu, Acyclic Edge Chromatic Number of Outerplanar Graphs
    8. W. Mader, Connectivity keeping paths in k-connected graphs,
    9. E. Rowland, Pattern avoidance in Binary trees.
    10. R. Yuster, A shortest cycle for each vertex of a graph
    11. S. Artmann and J. Harant, RANDOM PROCEDURES FOR DOMINATING SETS IN BIPARTITE GRAPHS.
    12. H. OKAMURA, "Multicommodity Flows in Planar Graphs", & "Three Commodity Flows in Graphs".
    13. C.R. Pranesachar, A class of matching-equivalent bipartite graphs.
    14. Justie Su-tzu Juan and Daphne Der-Fen Liu, Antipodal Labelings for Cycles
    15. Richard A. Brualdi, Susan Hollingsworth, Multicolored forests in complete bipartite graphs
    16. Salim El Rouayheb and Costas N. Georghiades, Graph Theoretic Methods in Coding Theory
    17. S. M. Cioaba, D. A. Gregory and W. H. Haemers, Matchings in regular graphs from eigenvalues
    18. Andras Gyarfas, Gabor N. Sarkozy, Andras Sebo and Stanley Selkow, Ramsey-Type Results for Gallai Colorings
    19. Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor Quadratic forms on graphs
    20. Noga Alon, Benny Sudakov, and Ayal Zaks, Acyclic Edge Colorings of Graphs
    21.T. Sager and S.J. Lin. A Prune Procedure for Exact Graph Coloring
    22. B. Birnbaum and C. Mathieu, "On-line Bipartite Matching Made Simple1
    23. Ro-Yu Wu, Jou–Ming Chang, Yue-Li Wang, Ranking and Unranking of t-ary Trees Using the Right Distance Representation
    24. Noga Alon, Radoš Radoičić, Benny Sudakov, Jan Vondrák, "A Ramsey-Type Result for the Hypercube.
    25.Istv´an Kov´acs and Mary Servatius,On Cayley Digraphs on Nonisomorphic 2-Groups.
    26. Michele Conforti, Gerard Cornuejols, Xinming Liu, Kristina Vuskovic and Giacomo Zambelli, Odd Hole Recognition in Graphs of Bounded Clique Size
    27. Linton C. Freeman, Stephen P. Borgatti, Douglas R. White. Centrality in valued graphs: A measure of betweenness based on network flow
    28. John E. Hopcroft and Richard M. Karp. An n^{5/2} algorithm for maximum matchings in bipartite graphs.
    29. Linton C. Freeman, Stephen P. Borgatti, Douglas R. White, Centrality in valued graphs: A measure of betweenness based on network flow
    30. Ioannis Gamvros, Luis Gouveia, S. Raghavan, Reload cost trees and network design.

    Topics to be covered

    (Updated regularly. Each topic will take about 1-2 weeks. )

    1. Basic Concepts in Graph Theory 1 week.

    Definitions, paths, cycles and trails, degree sequences, directed graphs, planar graphs, Hamilton cycles and Eular circuits.

    2. Trees and Algorithms 2 weeks.

    Cayley's theorem, spanning trees and the greedy algorithm, DFS and BFS, minimal spanning tree and shortest paths. Hook length formulas for binary trees.

    3. Matchings and Factors 3 weeks.

    Matchings and covers in bipartite graph, Hall's matching condition and SDR, Konig's minmax theorems, independent sets and dominating sets, maximal weight matching and stable matching, algorithms, Tutte's 1-factor theorem.

    4.Digraphs and Flows in Network 2 week.

    Digraphs, The Ford-Fulkerson Theorem, the integrality theorem, supply and demand

    5. Graph connectivity 1 week.

    Vertex connectivity, edge-connectivity, Menger's theorem

    6. Coloring of Graphs and Ramsey theorem 2 weeks.

    Brook's theorem, Ramsey's theorem and Ramsey numbers, Optional: view of Ramsey theory, Van der Waerden's theorem, density statement, and the compactness principle.

    7. Turan's theorem and extremal graph theory 0.5 week

    8. Linear algebra in graph theory 2 week

    Spectral of graphs, regular and line graph, Matrix tree theorem, de Brujin sequences, cycles and cut, Tutte polynomial

    Main References

    2. Modern graph Theory, by Bela Bollabas, Graduate Texts in Mathematics 182, Springer 1998.
    3. Algebraic Graph Theory, by Norman Biggs, Cambridge Universtiy Press, 1993.
    4. Introductory Combinatorics, by Richard Brualdi, fifth edition, Prentice Hall, 2010.
    5. Combinatorics: The Rota Way, by Kung, Rota and Yan, Cambridge University Press, 2009
    6. The Probabilistic Method, by Alon and Spencer, second edition, John Wiley & Sons, Inc, 2000.

    MAKE-UP POLICY: Make-ups for missed quizzes and exams will only be allowed for a university approved excuse in writing. Wherever possible, students should inform the instructor before an exam or quiz is missed. Consistent with University Student Rules , students are required to notify an instructor by the end of the next working day after missing an exam or quiz. Otherwise, they forfeit their rights to a make-up.

    POLICY FOR ABSENCES: Attendance on a regular basis is expected. While there are occasionally good reasons for you to choose to miss class, my experience has been that there is a strong correlation between attendance (as long as you are awake and listening) and performance in the course.

    For absence related to injure or illness, students who are absent from class three or more days should provide instructors with confirmation from a medical provider for an excused absence.

    SCHOLASTIC DISHONESTY: Copying work done by others, either in-cl ass or out of class, is an act of scholastic dishonesty and will be prosecuted to the full extent allowed by University policy. Collaboration on assignments, either in-class or out-of-class, is forbidden unless permission to do so is granted by your instructor. For more information on university policies regarding scholastic dishonesty, see University Student Rules .

    COPYRIGHT POLICY: All printed materials disseminated in class or on the web are protected by Copyright laws. One xerox copy (or download from the web) is allowed for personal use. Multiple copies or sale of any of these materials is strictly prohibited.