Hints and tips:
  • You may need to look up some unfamiliar terms in the title or description to get more of a sense of what is involved.
  • If the project has "No" in the "Current Availability:" field, it is already taken or not being offered this academic year but may be available again in future years.
  • The supervisor name links to a contact details webpage so, if you are interested, you can arrange to discuss this project or even propose a related topic of your own.
Level: MSci, MSc
Title: Saturated graphs
Supervisor:

Dr Robert Johnson
Research Area: Combinatorics
Description:

A graph G is H-saturated if it does not have H as a subgraph but the addition of any new edge to G creates a copy of H. The saturation number of H is the minimum number of edges an n vertex H-saturated graph can have. Results on the saturation number provide a counterpoint to the Turan type results of classical extremal graph theory. There are interesting results and questions on both the general kind of behaviour that the saturation number can exhibit, and its determination for particular graphs. There are many directions this project could take depending on the background and interests of the student.
Further Reading:
  • J. R. Faudree, R. J. Faudree, R. Schmitt, A Survey of Minimum Saturated Graphs, The Electronic Journal of Combinatorics Dynamic Survey 18 (2011).
Key Modules:

MTH6109 Combinatorics (desirable)
Other Information:
Current Availability: Yes