5
$\begingroup$

(Disclaimer: I am new here, so be patient with my mistakes, but I welcome corrections, advice or comments.)

I am interested in if anyone knows of ways of characterizing the orbits of an adjacency matrix of a multi-graph when it is conjugated by a permutation matrix. To clarify: The matrices in question are symmetric, with zero diagonal (sometimes called hollow symmetric), and all entries non-negative integers.

Conjugation by a permutation matrix will give another adjacency matrix with all the same properties. From a certain perspective this can be visualized as re-drawing the graph that gave rise to the adjacency matrix (in a manner that is isomorphic in the graph-theory sense).

I want to know if, given two adjacency matrices with the same dimensions, is it possible to determine if they lie in the same orbit (without re-constructing the necessary permutation matrices). However, I am interested in any results that are related to this question, since I believe the answer is not known (correct me if I am wrong here).

  • 0
    @ Jack Schmidt - Though I didn't realize it at the time, that is what I was looking for. I knew a lot of research had been done in the area, but I just didn't know how to find it. (There are numerous ways to characterize the problem, it has implications for the reconstruction problem, Hamiltonian circuits, arbitrary subgraphs, and probably many more. Thanks for the practical workaround.2012-04-11

1 Answers 1

3

You are asking for an algorithm to determine if two multigraphs given by adjacency matrices are equivalent. The problem of graph isomorphism is a notorious one in complexity theory, since it is only known to sit somewhere inbetween P and NP, but it is not known if it is P or NP.

From this it is clear that the problem is not an easy one. The best existing program for graph isomorphism problems is nauty. However, I don't know if it supports multigraphs out of the box. There are interfaces to nauty in Sage and Magma.