IsomorphicGraphQ

IsomorphicGraphQ[g1,g2]

yields True if the graphs g1 and g2 are isomorphic, and False otherwise.

Details

  • IsomorphicGraphQ is also known as graph isomorphism problem.
  • IsomorphicGraphQ is typically used to determine whether two graphs are structurally equivalent.
  • Two graphs are isomorphic if there is a renaming of vertices that makes them equal.
  • IsomorphicGraphQ[g1,g2,] gives True if all the gi are isomorphic.

Examples

open allclose all

Basic Examples  (1)

Test whether two graphs are isomorphic:

Find an isomorphism that maps g to h:

Renaming the vertices of graph g gets an equal graph as h:

Scope  (4)

IsomorphicGraphQ works with undirected graphs:

Directed graphs:

IsomorphicGraphQ gives False for non-isomorphic graphs:

As well as non-graph expressions:

IsomorphicGraphQ works with large graphs:

Properties & Relations  (10)

Isomorphic graphs have the same number of vertices and edges:

The isomorphic graphs have the same ordered degree sequence:

The graphs with the same degree sequence can be non-isomorphic:

FindGraphIsomorphism can be used to find the mapping between vertices:

Highlight and label two graphs according to the mapping:

Permuting the vertices in a graph produces an isomorphic graph:

The graph generated by the permutation of its adjacency matrix is isomorphic to itself:

Sample a permutation of the vertex list:

The line graph of a cycle graph is isomorphic to itself:

The line graph of a path is isomorphic to :

The complement of the line graph of is isomorphic to a Petersen graph:

Two connected graphs are isomorphic iff their line graphs are isomorphic:

With one exception:

The non-isomorphic directed graphs can have undirected graphs that are isomorphic:

Wolfram Research (2010), IsomorphicGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html (updated 2012).

Text

Wolfram Research (2010), IsomorphicGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html (updated 2012).

CMS

Wolfram Language. 2010. "IsomorphicGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2012. https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html.

APA

Wolfram Language. (2010). IsomorphicGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html

BibTeX

@misc{reference.wolfram_2024_isomorphicgraphq, author="Wolfram Research", title="{IsomorphicGraphQ}", year="2012", howpublished="\url{https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html}", note=[Accessed: 12-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_isomorphicgraphq, organization={Wolfram Research}, title={IsomorphicGraphQ}, year={2012}, url={https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html}, note=[Accessed: 12-December-2024 ]}