Finite-type invariants for graphs and graph reconstructions

Many of the fundamental open problems in graph theory have the following general form: How much information does one need to know about a graph G in order to determine G uniquely. In this article we investigate a new approach to this sort of problem motivated by the notion of a finite-type invariant...

Full description

Saved in:
Bibliographic Details
Published in:Advances in mathematics (New York. 1965) 2004-08, Vol.186 (1), p.181-228
Main Author: Forman, Robin
Format: Article
Language:English
Subjects:
Finite-type invariants
Graph reconstruction
Graph theory
Nash-Williams lemma
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many of the fundamental open problems in graph theory have the following general form: How much information does one need to know about a graph G in order to determine G uniquely. In this article we investigate a new approach to this sort of problem motivated by the notion of a finite-type invariant, recently introduced in the study of knots. We introduce the concepts of vertex-finite-type invariants of graphs, and edge-finite-type invariants of graphs, and show that these sets of functions have surprising algebraic properties. The study of these invariants is intimately related with the classical vertex- and edge-reconstruction conjectures, and we demonstrate that the algebraic properties of the finite-type invariants lead immediately to some of the fundamental results in graph reconstruction theory.
ISSN:0001-8708
1090-2082
DOI:10.1016/j.aim.2003.08.013