Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Completeness and Universality Properties of Graph Invariants and Graph Polynomials
event speaker icon
Ilia Averbouch, Ph.D. Thesis Seminar
event date icon
Wednesday, 20.10.2010, 14:00
event location icon
Taub 601
Graph polynomials are powerful and well-developed tools to express graph parameters. Usually graph polynomials are compared to each other by ad-hoc means allowing to decide whether a newly defined graph polynomial generalizes (or is generalized) by another one. We study their distinctive power and introduce the notions of $dp$-completeness and universality of graph polynomials in order to formalize dependencies between them. Many known graph polynomials satisfy linear recurrence relations with respect to some set of edge- or vertex-elimination operations. Inspired by the work of Brylawski and Oxley on the Tutte polynomial, we define several classes of graph polynomials according to their recurrence relations, and prove $dp$-completeness and universality results for those classes. The talk is self-contained and does not require any prior knowledge on graph polynomials.
[Back to the index of events]