Graph Theory and Design Theory

University of Queensland

Course Description

  • Course Name

    Graph Theory and Design Theory

  • Host University

    University of Queensland

  • Location

    Brisbane, Australia

  • Area of Study


  • Language Level

    Taught In English

  • Prerequisites


  • Course Level Recommendations


    ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.

    Hours & Credits

  • Host University Units

  • Recommended U.S. Semester Credits
  • Recommended U.S. Quarter Units
  • Overview

    Course Description
    Various topics in Graph Theory including a selection from graph algorithms, connectivity, networks, planarity, graph colouring, graph symmetries. An introduction to Design Theory including a selection of topics from Latin squares, Steiner triple systems, balanced incomplete block designs, graph decompositions, projective and affine designs.


    Course Introduction
    This  course deals with both graph theory and combinatorial design theory, and should allow students subsequently to read further in these areas, and to apply their knowledge of graph theory and design theory to other appropriate fields.

    Graph theory is one branch of the wide-ranging field known nowadays as combinatorics. It has applications in many different areas, including parts of computer science, operations research including scheduling, network flows and circuit design.

    Design theory is another branch of combinatorics. Its traditional roots are in the design of experiments, but it has found recent applications in cryptography, coding theory and communication networks.


    Learning Objectives
    After successfully completing this course you should be able to:

    1. understand the basics of graph theory and combinatorial design theory and their relevance to the real world
    2. understand important concepts in graph theory such as Eulerian and Hamiltonian graphs, graph connectivity, spanning trees, graph factorisation and planarity
    3. understand the theory of extremal graphs.
    4. understand the concept of networks, flows in networks, and some algorithms used to calculate maximum flows.
    5. understand the definition of and some construction techniques for balanced incomplete block designs.
    6. understand construction techniques for Steiner Triple Systems.
    7. understand the definitions of, and connections between, pairwise balanced designs, group divisible designs, transversal designs, orthogonal arrays and Latin squares.
    8. appreciate the close connection between graph theory and design theory


    Course Contact
    3 Lecture hours, 1 Tutorial hour

Course Disclaimer

Courses and course hours of instruction are subject to change.

Eligibility for courses may be subject to a placement exam and/or pre-requisites.

Some courses may require additional fees.

Credits earned vary according to the policies of the students' home institutions. According to ISA policy and possible visa requirements, students must maintain full-time enrollment status, as determined by their home institutions, for the duration of the program.