Technical Report PHD-2011-05

Title: Completeness and Universality Properties of Graph Invariants and Graph Polynomials
Authors: Ilia Averbouch
Supervisors: Johann A. Makowsky
Abstract: 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 these classes. We also extend our results to classes of labeled graph polynomials.

We provide several observations regarding computational complexity of the discussed dp-complete graph polynomials. Notably, we exploit definability properties of these polynomials to show that they can be computed efficiently when input graphs are limited by a certain parameter and present some explicit algorithms.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2011
To the main CS technical reports page

Computer science department, Technion