Australian National University
September 3 & 13, 2008
Recursive Structure of Planar Graph Classes(September 3)
ABSTRACT: A recursive characterisation of a class of graphs consists of a set of starting graphs in the class, together with a set of operations that modify one graph in the class to form another. It is required that every graph in the class can be obtained from some starting graph by performing a finite sequence of operations. Recursive characterisations can be used to prove properties of the graph class by induction, and can also be used to exhaustively generate the class on the computer.
In this talk we survey previous recursive characterizations of various classes of planar graphs. Then we present two new results. One is the recursive characterisation of simple 5-regular planar graphs, and the other is the recursive characterisation of fullerenes (all known as buckeyballs). The latter are planar cubic graphs with faces of size five and six, and are of considerable importance in chemistry. (Joint work with Mahdieh Hasheminezhad and Tristan Reeves).
Generation of Combinatorial Objects( September 13)
ABSTRACT:Many applications require the exhaustive generation on the computer of all the objects in a particular class. A key issue in this task is the removal of isomorphic copies. Very many techniques of particular or general applicability have been developed. In this talk we will concentrate on methods that work for many types of object, such as graphs with various properties. These include the orderly method and the canonical augmentation method. Examples will include fullerenes and Latin squares.
|Time and Date:
Wednsday, September 3, 2008 - 11:00-12:00
Saturday, September 13, 2008 - 14:00-15:00
|Place: Lecture Hall, Niavaran Bldg., Niavaran Sqr., Tehran, Iran