Graph Polynomials
Introduction
Graph polynomials are invariants of graphs (i.e. functions of graphs that
are invariant with respect to graph isomorphism); they are usually polynomials
in one ore two variables with integer coefficients. Graph polynomials can
be interpreted as ordinary generating functions for the coefficient sequences
which count in most cases certain subgraphs. Some polynomials (e.g. the
chromatic polynomial) are defined by their values. Important examples of
graph polynomials are
Computation
The calculation of many graph polynomials is an NP-hard (#P) problem. The
only exception of the above given list is the characteristic polynomial
which can be calculated in polynomial time. There are different ways to
perform graph polynomial computations:
-
complete enumeration of all relevant subgraphs
-
application of edge or vertex decomposition formulae
-
reduction techniques (e.g. series, parallel, delta-star)
-
splitting of graphs i.e. using separating vertex sets
-
tree or path decomposition (yields polynomial time algorithms in graphs
of restricted treewidth)
Examples
The following polynomials are obtained with the GraphEditor
by André Pönitz. It uses the composition method based on path
decompositions of graphs.
Hint: You will find a link to each graph and to polynomials
computed here. The structure of a graph is stored as a reduced adjacency
list (.txt file). The first line contains the number of vertices and edges.
The vertices are numbered 1,...,n. The following lines start with
a vertex number followed by adjacent vertices. However, each edge is presented
only once in this list. (If v appears in the adjacency list of u
then u does not appear in the adjacency list of v.)