Graph invariant

A graph can be given graphically in the form of a graph drawing. But a given graph may be drawn in several equivalent ways and even for small graphs it is often hard to decide if two drawings represent the same graph, that is if two graphs are isomorphic.

When manipulating graphs in a computer, depending on the data structure used, the vertices and the edges of the graph have to be labeled. There is no canonical way to label a graph and a common problem is to decide if two graph structures are isomorphic.

Proving that two given graph presentations are not isomorphic is often done by showing that one graph has a certain graph invariant the other graph lacks.

Graph invariants

• number of vertices
• number of edges

• vertex chromatic number - minimum number of colors needed to color all vertices so that adjacent vertices have a different color
• edge chromatic number - minimum number of colors needed to color all edges so that adjacent edges have a different color
• edge covering number - minimal number of edges needed to cover all vertices
• vertex covering number - minimal number of vertices needed to cover all edges