Elementary Properties

To find heuristics for partitioning, we look for graph invariants, which are properties of a graph which does not change under isomorphism.  Two basic graph invariants are order and size.

Proposition 1

If two graphs and are isomorphic, then and .

Proof

If is a bijective isomorphic mapping, then must equal by the definition of a bijection.  Proving is equally easy.

Another useful graph invariant is the sequence of degrees of the vertices.  Grouping vertices by ascending degree is a straightforward partitioning method.

Proposition 1, continued.

If and are the vertex degrees in the isomorphic graphs G and G′ respectively, then
.

Proof

For any vertex , ??? the vertices adjacent to v are mapped onto the vertices in that are adjacent to .  Thus, .  More importantly, the degree of v is equal to the degree of .

Proposition 1 is a very simple statement among those that are used by a method called the refining technique.  Other statements of the same kind are given in the three collaborative problems.

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.