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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:105-qucosa-94991 |
| Date | 19 September 2012 |
| Creators | Trinks, Martin |
| Contributors | TU Bergakademie Freiberg, Mathematik und Informatik, Prof. Dr. Ingo Schiermeyer, Prof. Dr. Peter Tittmann, Prof. Dr. Ingo Schiermeyer, Prof. Dr. Peter Tittmann |
| Publisher | Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola" |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis |
| Format | application/pdf |
Page generated in 0.0893 seconds