Graph Theory

Dozentin: Dr. Lucia Draque Penso
Übungsleiterin: Elena Mohr

Time
Monday 12:15-13:45 in Heho22 E.04 (class)
Thursday 10:15-11:45 in Heho18 120 (class)

Wednesday 14:15-15:45 in Heho18 120 (exercise class)

The class starts on Monday, the 14th of October. There will be a class instead of an exercise class on Wednesday, the 16th of October.

Exam
There will be a written exam at the end of the lecture time as well as at the beginning of the summer semester. Getting 50% of the points of the exercise sheets is a prerequisite for the admission to the exam.

General comments
The lecture 'Graph Theory' is an introductory lecture, necessary for more advanced Topics ('Graph Theory 2') and helpful in the understanding of related courses, such as those regarding optimization, probabilistic methods, networking and distributed computing.

A graph may be seen as a network of elements linked by some sort of (bilateral or unilateral) relationship defining neighborhood, in which one may investigate a miscellaneous of structural properties. For instance, in social networks, one may want to find the minimum sets of elements capable to make a propagation to all happen, or, in computer networks, one may want to find the fastest way to route a message, or yet, in resource allocation, one may want that no two neighbors provide the same service, so that it gets less locally concentrated and more spreadout through the network.  As we will see, there is a number of theoretical results with practical applications in both allocation and (computer or social) networking.  

Literature
R. Diestel, Graphentheorie, 4te Auflage, Springer 2010.
B. Bollobas, Modern Graph Theory, Springer 1998.
J.A. Bondy und U.S.R. Murty, Graph Theory, Springer 2008.
J.A. Bondy und U.S.R. Murty, Graph Theory with Applications, 1976.
D.B. West, Introduction to Graph Theory, Prentice-Hall 2005.
L. Volkmann, Graphen an allen Ecken und Kanten, 2011.