6
$\begingroup$

Q: Is there a graph matrix-representation (not necessarily an $n \times n$ matrix for an $n$-graph) such that isospectrality implies graph-isomorphism? For instance, would the simple distance-matrix do the job?

Background: The 'can you hear the shape of a drum?' question can be answered of undirected graphs in the negative, but I do not know if the results are only for the adjacency and/or Laplacian matrix representations.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Note that existence of such matrix which is polynomially computable would imply polynomial GI test. Hence the matrix is probably large, or at least hard to compute. $\endgroup$
    – Mikhail Tikhomirov
    Commented Oct 27, 2017 at 1:12
  • $\begingroup$ Hi Mikhail - thanks for your comment. What is a 'GI test'? $\endgroup$
    – Andrew Whelan
    Commented Oct 27, 2017 at 1:21
  • 1
    $\begingroup$ Graph isomorphism test. $\endgroup$
    – Mikhail Tikhomirov
    Commented Oct 27, 2017 at 1:22
  • 3
    $\begingroup$ Distance matrix is easily computable in $O(|V||E|)$ time (could be faster for some graph classes). There are examples of non-isomorphic graphs with same distance matrices spectrum (for a lot of interesting examples and info see here). $\endgroup$
    – Mikhail Tikhomirov
    Commented Oct 27, 2017 at 2:10
  • 1
    $\begingroup$ After some reflection, the answer seems to be a trivial 'yes'. We know there is an upper bound on computational complexity, say $f(n)$. If we imagine such an algorithm and each step in the process as a 'yes-no' type procedure, then we simply encode this in an $(f(n) \times f(n))$ diagonal matrix with binary entries on the diagonal. I'm finding it hard to think why this would fail but it should be easy to imagine fixing it. $\endgroup$
    – Andrew Whelan
    Commented Oct 27, 2017 at 15:01

2 Answers 2

Reset to default
3
$\begingroup$

Here is a ridiculous solution using a $1 \times 1$ matrix! First, encode an $n \times n$ adjacency matrix $A$ by $a \lt 2^{\binom{n}2}$ where $a$ is the binary integer obtained by listing the above diagonal entries row by row. If you just want isospectrality to imply isomorphism then just encode it as $[a].$

Assuming that you want isospectrality equivalent to idomorphism, consider all $n!$ adjacency matrices getting an multi-set of $n!$ integers which we can give the natural order. Finally, encode the graph as the $1\times 1$ matrix $[2^{a_1+1}3^{a_2+1}\cdots]$ using the first $n!$ primes. The $+1$ is an inelegant way to avoid edge free graphs of various sizes being represented by $[1].$

This could be greatly enhanced, for example use instead the base $3$ integer with $n!-1$ $2$’s separating $a_12a_22a_32\cdots.$

‘Actually, one could just use the lexicographically least $n \times n$ adjacency matrix. This would have the vertices in decreasing order of degree. That alone is no help for regular graphs, but for others it might cut the number of cases.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I suppose this could even be encoded as a $1\times 1$ matrix whose entry is an element of $\mathbb{Q}\cap[0,1]$ by encoding the adjacency matrix as a binary decimal. $\endgroup$
    – Neal
    Commented Nov 28, 2017 at 13:30
2
$\begingroup$

Distance matrix is not going to help, as examples of non-isomorphic co-spectral strongly regular graphs would tell you. The smallest examples like this exist on 16 vertices: Shrikhande graph.

In general, there seem to be logic-related obstacles for non-isomorphism certificates of this sort, related to 1st order logics with counting. This has started with the famous paper An Optimal Lower Bound on the Number of Variables for Graph Identification by Cai, Furer and Immerman.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .