Return to search

Graph polynomials and their representations

Graph polynomials are polynomials associated to graphs that encode the number of subgraphs with given properties. We list different frameworks used to define graph polynomials in the literature. We present the edge elimination polynomial and introduce several graph polynomials equivalent to it. Thereby, we connect a recursive definition to the counting of colorings and to the counting of (spanning) subgraphs. Furthermore, we define a graph polynomial that not only generalizes the mentioned, but also many of the well-known graph polynomials, including the Potts model, the matching polynomial, the trivariate chromatic polynomial and the subgraph component polynomial. We proof a recurrence relation for this graph polynomial using edge and vertex operation. The definitions and statements are given in such a way that most of them are also valid in the case of hypergraphs.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:105-qucosa-94991
Date19 September 2012
CreatorsTrinks, Martin
ContributorsTU Bergakademie Freiberg, Mathematik und Informatik, Prof. Dr. Ingo Schiermeyer, Prof. Dr. Peter Tittmann, Prof. Dr. Ingo Schiermeyer, Prof. Dr. Peter Tittmann
PublisherTechnische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola"
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:doctoralThesis
Formatapplication/pdf

Page generated in 0.0016 seconds