Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 01, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Johann A. Makowsky (Technion, Haifa)
Iteration graphs are graph families Gn : n ∈ N constructed from an initial graph G0 by the repeated application of a fixed graph operation. Simple examples are the paths on n vertices Pn or the rectangular (m × n)-grids Gm,n for fixed m.
N.L. Biggs, R.M. Damerell and D.A. Sands (1972) initiated the study the behaviour of the Tutte polynomial on specific iteration graphs. They showed that in these cases the polynomials T(Gn) satisfy a linear recurrence relation. M. Noy and A. Ribó (2004) extended this observation to a larger class of iteration graphs.
In our work we show that this phenomenon is shared by a wide class of graph polynomials, the MSOL-definable graph polynomials, which include the matching polynomials, the clique and independent set polynomials, the colored Tutte polynomials and many Farrel polynomials. This also includes the Jones polynomial and the Kauffman brackets for knots. We also show that the class of iteration graphs can be generalized and extended to arbitrary relational structures and corresponding generalizations of graph polynomials.
Joint work with Eldar Fischer.
Automatic MiSe System Software Version 1.4803M | admin login