Labeled Graphs

The refining technique is easily generalized to graphs whose vertices and/or edges are labeled. The labels can be of an arbitrary nature. Traditionally labels are called colors, so we say that the graph is colored. For chemical graphs that represent molecules, the colors of the vertices are names of the atoms. The edges of the chemical graphs are often labeled with integers to show the ordinary links, or double links, etc. Normally, the links are not more than tripled. Sometimes, instead of showing the labels of the edges, we duplicate the edges as on the figure.

Formal Definition

Two colored graphs and are called isomorphic if there is a bijective mapping from onto such that
  1. for every , the colors of and are the same;
  2. for any two vertices , there is a one-to-one correspondence between the edges connecting with and those connecting with so that the corresponding edges have the same color.
If the vertices and/or edges have no labels, then they can be given a special label different from the rest.  Thus, we can always assume that all vertices and all edges are colored.
Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.