2
$\begingroup$

I'm examining isomorphisms of simple finite undirected graphs.

In order to test whether or not two graphs are isomorphic, there are a lot of "simple" tests one can do, namely, compare the number of vertices, number of edges, degree sequences, and look for edge cycles. In addition to this, there are a few examples of graphs for which efficient isomorphism tests are known, Wikipeda lists a few examples of this, including, for example, planar graphs.

What are some good examples of pairs of graphs that are not isomorphic, but pass all the simple tests for isomorphism, and don't fall into a class of graphs for which a polynomial-time algorithm is known?

$\endgroup$
2
$\begingroup$

One class of examples comes from Latin square graphs. If $L$ is an $n\times n$ Latin graphs, take the graph with the $n^2$ triples $(i,j,L_{i,j})$ as vertices, with two triples adjacent if they agree on one of the three coordinates. The graphs from distinct Latin squares are isomorphic if the Latin squares are isotopic, but the Latin squares arising as the multiplication tables of finite groups are isotopic if and only if the groups are isomorphic. The smallest relevant examples occur on 16 vertices.

For a second class, start with an $n\times n$ Hadamard matrix. We construct a bipartite graph on $4n$ vertices. The first step is to convert the Hadamard matrix to a 01-matrix of order $2n\times 2n$, but replacing each entry by a $2\times2$ matrix as follows: $0$ becomes the $2\times2$ zero matrix, 1 becomes the $2\times2$ identity matrix and $-1$ becomes \[ \begin{pmatrix}0&1\\ 1&0 \end{pmatrix}. \] Denote the resulting matrix by $\tilde{H}$. The Hadamard graph is the bipartite graph with adjacency matrix \[ \begin{pmatrix} 0&\tilde{H}\\ \tilde{H}^T&0\end{pmatrix}. \] The Hadamard graphs are isomorphic if and only if the Hadamard matrices are equivalent )permutations of rows and columns, rescaling. There are five equivalence classes of Hadamard matrices of order 16, giving non-isomorphic graphs on 64 vertices.

For both families the graphs produced will be cospectral when the input matrices are of the same order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.