15
$\begingroup$

For the sake of this question, a graph here has a finite number of vertices, with undirected simple edges, no loop, and no weight or label on edges or vertices. Therefore, its adjacency matrix $A=[a_{i,j}]$ is a symmetric matrix with entries in $\{0,1\}$, and $0$ on the main diagonal.

Assuming that $A^2$ is known, can we recover $A$?

The question comes from my self-study of graph theory and I have no idea on how to solve this question. What I know:

  1. Let's label the vertices of the graph as $v_1$, $v_2$, $\dots$, $v_n$ so that $a_{i,j}=1$ if there is an edge between $v_i$ and $v_j$, and $0$ otherwise. Then, if $a_{i,j}^{(k)}$ is the entry of $A^k$ at row $i$ and column $j$, $a_{i,j}^{(k)}$ is the number of walks of length $k$ between $v_i$ and $v_j$. Therefore, what is known in the problem are the numbers $a_{i,j}^{(2)}$ of common neighbors between $v_i$ and $v_j$.
  2. If the $i$th row of $A^2$ is composed of $0$s, then $v_i$ is an isolated point of the graph. (If $v_i$ is not isolated, then there is a walk $v_i-v_j-v_i$ so $a_{i,i}^{(2)}\ge 1$). So we can simplify the problem by assuming that the graph has no isolated point.
  3. $a_{i,i}^{(2)}=1$ is equivalent to $\deg(v_i)=1$ (end vertex).
  4. There are results about square roots of positive semi-definite matrices, but $A^2$ is not positive semi-definite, and the square root would not have its entries in $\{0,1\}$.
  5. For $n=3$, by looking at the squares of the adjacency matrices of the few possible graphs with $3$ vertices, the answer is yes.

In my question, I assume that it is known that $S=A^2$ is the square of the adjacency matrix of a graph and I wonder if there is another graph whose adjacency matrix has also $S$ for square. So a reformulation of the question is

Does it exist two adjacency matrices $A$ and $B$ (as defined in the first paragraph) such that $A^2=B^2$?

$\endgroup$
4
  • $\begingroup$ Your last bolded question may need disambiguation - "two adjacency matrices for non-equivalent graphs". $\endgroup$
    – Nij
    Jan 26 at 8:08
  • $\begingroup$ If there is actually non-uniqueness of squares of graphs, my hunch is that counterexamples can be found among bipartite graphs. $\endgroup$ Jan 26 at 8:11
  • $\begingroup$ Section 3 in this article seems to address your question. This MSE post might also be relevant. $\endgroup$
    – Sil
    Jan 26 at 10:54
  • $\begingroup$ I deleted my answer, it was stupid $\endgroup$
    – caduk
    Jan 26 at 13:00

2 Answers 2

13
$\begingroup$

The answer is no - you cannot recover the graph.

You state that what is known is the number of common neighbours between any two vertices. There is a nice class of graphs, Strongly regular graphs, which are essentially defined according to how many common neighbours any pair of vertices have. In particular, a graph is an $(n,k,\lambda, \mu)$ strongly regular graph if it has $n$ vertices, is $k$-regular, every pair of adjacent vertices has $\lambda$ common neighbours, and every pair of nonadjacent vertices has $\mu$ common neighbours.

Per the wikipedia article linked (or just by direct calculation with the above parameters), the adjacency matrix $A$ of an $(n,k,\lambda, \mu)$ strongly regular graph satisfies:

$$A^2 = kI + \lambda A + \mu(J-I-A)$$

Where $J$ is an all $1$s matrix, and I is the $n\times n$ identity matrix.

Thus, any two strongly regular graphs with the same parameters, in which $\lambda = \mu$, have the same squared adjacency matrix! To see this, suppose $\lambda = \mu$, and re-arrange the above equation to get:

$$A^2 = kI + \lambda A + \lambda(J-I-A)$$ $$A^2 = kI + \lambda A + \lambda(J-I) - \lambda A$$ $$A^2 = kI + \lambda(J-I)$$

And indeed there are two strongly regular graphs, with the same parameters, that have $\mu = \lambda$. They are the (4,4) Rook Graph and the Shrikhande Graph, both of which are $(16,6,2,2)$ strongly regular graphs.

$\endgroup$
9
$\begingroup$

Taking $n=4$: any graph consisting of two disjoint edges gives $A^2=I$. There are $3$ such graphs on a given vertex set of size $4$ (but of course they are all isomorphic).

For an example of two non-isomorphic graphs giving the same square: let $n=6$, and consider either a $6$-cycle graph, or a graph consisting of two disjoint $3$-cycles.

$\endgroup$
6
  • 1
    $\begingroup$ I don't understand your example for n = 6: a disjoint union of two 3-cycles has adjacency matrix which is a direct sum (of two 3x3 matrices), while a 6-cycle does not, and the squares of their adjacency matrices don't even have the same zero pattern $\endgroup$
    – math54321
    Jan 26 at 22:07
  • 1
    $\begingroup$ @math54321If the 6-cycle looks like $1-2-3-4-5-6-1$, then organise the rows and columns so that the first 3 rows / columns correspond to vertices 1,3,5 and the last 3 correspond to 2,4,6. In particular, letting $X$ and $Y$ be the two squared adjacency matrices, there's a permutation matrix $P$ (that performs the swap mentioned in sentence 1 of this comment) such that $X$ and $Y$ are similar via $P$: so $X = PYP^{-1}$. $\endgroup$ Jan 27 at 7:20
  • 2
    $\begingroup$ @math54321 The two graphs could be $\{1-2-3-4-5-6-1\}$ and $\{1-3-5-1 \,, \,2-4-6-2\}$. Isn't it the case that for any $i$ and $j$, the number of length-$2$ walks from $i$ to $j$ is the same in both graphs? $\endgroup$ Jan 27 at 7:21
  • $\begingroup$ Ah I see @BrandonduPreez and responded almost simultaneously :) $\endgroup$ Jan 27 at 7:22
  • $\begingroup$ Thanks @BrandonduPreez and James for the clarification. I think it's important to specify the exact graph (labeled with edges/vertices) when talking about the adjacency matrix, not just the isomorphism type of the graph (which only gives the adjacency matrix up to conjugation by permutation matrices) $\endgroup$
    – math54321
    Jan 27 at 17:29

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.