Graph Invariants and Graph Isomorphism
Easily computable graph invariants are instrumental for fast recognition of graph isomorphism, or rather non-isomorphism, since for any invariant at all, two graphs with different values cannot (by definition) be isomorphic. Two graphs with the same invariants may or may not be isomorphic, however.
A graph invariant I(G) is called complete if the identity of the invariants I(G) and I(H) implies the isomorphism of the graphs G and H. Finding such an invariant would imply an easy solution to the challenging graph isomorphism problem. However, even polynomial-valued invariants such as the chromatic polynomial are not usually complete. The claw graph and the path graph on 4 vertices both have the same chromatic polynomial, for example.
Read more about this topic: Graph Property
Famous quotes containing the word graph:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)