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

The Taub Faculty of Computer Science Events and Talks

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
event speaker icon
Advisor: Prof. J. A. Makowsky
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.