Given a simple graph $G$ and its adjacency matrix $A$, one may naturally consider the following graph $A_G$:


$E(A_G)=\{\{(i,j),(k,l)\}\in2^{V(A_G)}:(|i-k|=1\text{ and }j=l)\text{ or }(i=k\text{ and }|j-l|=1)\}$

Here's an example showing how $A_G$ can be used. Let $G$ be a tree and $V(G)=\{1,...,n\}$. If $A_G$ is a path, then one may easily show that the set $\{|i-j|:\{i,j\}\in E(G)\}$ has $n-1$ elements. The latter implies $G$ is graceful. On the other hand, we can prove that $G$ is a caterpillar iff we can write $A$ in such way that $A_G$ becomes a path. This gives us another proof of the well-known result that all caterpillars are graceful.

Informally, $A_G$ is a picture prescribed to $G$, and one may wish to study its symmetries (that is $\text{Aut} A_G$). My question is whether it was studied before how properties of $G$ correlate with properties of $A_G$. I'll be also glad if you point out some other examples.



You must log in to answer this question.