The Algebra of Graph Invariants - Lower and Upper Bounds for Minimal Generators

Details The Algebra of Graph Invariants - Lower and Upper Bounds for Minimal Generators The Algebra of Graph Invariants - Lower and Upper Bounds for Minimal Generators

2007-12-02

arxiv.org/abs/0712.0142v2

Mathematics

Combinatorics

25 pages, 3 figures

Scientific paper

In this paper we study the algebra of graph invariants, focusing mainly on the invariants of simple graphs. All other invariants, such as sorted eigenvalues, degree sequences and canonical permutations, belong to this algebra. In fact, every graph invariant is a linear combination of the basic graph invariants which we study in this paper. To prove that two graphs are isomorphic, a number of basic invariants are required, which are called separator invariants. The minimal set of separator invariants is also the minimal basic generator set for the algebra of graph invariants. We find lower and upper bounds for the minimal number of generator/separator invariants needed for proving graph isomorphism. Finally we find a sufficient condition for Ulam's conjecture to be true based on Redfield's enumeration formula.

Affiliated with

Also associated with

No associations

Rating

The Algebra of Graph Invariants - Lower and Upper Bounds for Minimal Generators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Algebra of Graph Invariants - Lower and Upper Bounds for Minimal Generators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Algebra of Graph Invariants - Lower and Upper Bounds for Minimal Generators will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469419