Sign up to our mailing list by sending a blank email to invariantsociety-subscribe@maillist.ox.ac.uk

Graph Theory: an Introduction to Cycle Spectra

Lauren Kutler, Undergraduate Mathematics Seminar

Date Icon Week 8, Wednesday 7 March HT 2012
Time Icon 8:15pm

One attribute of graphs that can be investigated is cycle length. Roughly, a graph has a cycle of length n if you can pick some vertex, then travel along n edges back to that initial vertex without going through the same vertex twice (excepting, of course, the initial vertex). One ‘interesting’ kind of graph has all possible different cycle lengths. We call such a graph pancyclic. Graph Theorists have been studying these graphs for the past 40 years or so, asking questions such as what conditions guarantee pancyclicity in an arbitrary graph. Recently, there has been some interest in a modification of this kind of question, asking instead what conditions guarantee that a graph has at least p different cycles lengths, where |p| has been dubbed the ‘cycle spectrum’ of the graph. I had the privilege of investigating this question during a summer research project. I will discuss our findings along with some of the background preceding our research, as well as other current work. The talk should be very accessible to mathematicians in any year (and hopefully interesting too).