Editing Graph isomorphism (section)

==Variations==
In the above definition, graphs are understood to be [[directed graph|undirected]] [[labeled graph|non-labeled]] [[weighted graph|non-weighted]] graphs. However, the notion of isomorphism may be applied to all other variants of the notion of graph, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception.

===Isomorphism of labeled graphs===
For [[labeled graph]]s, two definitions of isomorphism are in use.

Under one definition, an isomorphism is a vertex bijection which is both edge-preserving and label-preserving.<ref>[https://books.google.com/books?id=14138OJXzy4C&pg=PA424 p.424]</ref><ref>{{cite book | chapter-url=https://link.springer.com/chapter/10.1007/11751649_46 | doi=10.1007/11751649_46 | chapter=Efficient Method to Perform Isomorphism Testing of Labeled Graphs | title=Computational Science and Its Applications - ICCSA 2006 | series=Lecture Notes in Computer Science | date=2006 | last1=Hsieh | first1=Shu-Ming | last2=Hsu | first2=Chiun-Chieh | last3=Hsu | first3=Li-Fu | volume=3984 | pages=422–431 | isbn=978-3-540-34079-9 }}</ref>

Under another definition, an isomorphism is an edge-preserving vertex bijection which preserves equivalence classes of labels, i.e., vertices with equivalent (e.g., the same) labels are mapped onto the vertices with equivalent labels and vice versa; same with edge labels.<ref>Pierre-Antoine Champin, Christine Solnon, [https://link.springer.com/chapter/10.1007/3-540-45006-8_9 "Measuring the Similarity of Labeled Graphs"] in:  ''[[Lecture Notes in Computer Science]]'', vol. 2689, pp 80–95</ref>

For example, the <math>K_2</math> graph with the two vertices labelled with 1 and 2 has a single automorphism under the first definition, but under the second definition there are two auto-morphisms.

The second definition is assumed in certain situations when graphs are endowed with ''unique labels'' commonly taken from the integer range 1,...,''n'', where ''n'' is the number of the vertices of the graph, used only to uniquely identify the vertices. In such cases two labeled graphs are sometimes said to be isomorphic if the corresponding underlying unlabeled graphs are isomorphic (otherwise the definition of isomorphism would be trivial).