This has now evolved somewhat (and I realise at this point that my terminology and approach in this question needed some improvement). For anyone interested, the inverse operation has some implications to topological systems in physics. We have published our work in Physical Review B and are fortunate enough for it to be an Editor's Suggestion and a featured article in APS Physics. Link: journals.aps.org/prb/abstract/10.1103/PhysRevB.95.165109

Re: confusion over polynomials definition - I made a typo in the summation, which I have now fixed. Each $i$th term of course has the matrix raised to the power $i $

(As a "practical" example in my specific setting: those same rules apply on a honeycomb tight binding lattice but the 2nd nearest edges are described with $C^2-3C^0$. Setting $x=0$ and choosing some $y,z$, one gets the nearest-and-next-nearest energy spectrum of the honeycomb purely by analysis of the nearest-neighbour only system. The eigenstates are of course identical.)

In my case, negative edges are indeed allowed. Consider a simple cycle graph $C$ with vertex weight 0 and edge weight 1. $C^2$ would have vertex weights 2 and edges of weight 1 between "2nd nearest neighbours". $C^0$ would have no edges, and vertices with unit weight. Under the same rules as matrix addition, $C^2 - 2C^0$ would have such edges but vertices of weight 0. You can describe a graph with some vertex weight, nearest-edges and next-nearest edges with $C' = xC^0 + yC + z(C^2 - 2C^0)$. The corresponding eigenspectrum $eig(L(C')) = \{x + yE + z(E^2 - 2) | E \in eig(L(C))\}$.

I'm sorry about my terminology. I mean the eigenspecrum of $L(G)$ in both cases. Take some real polynomial A. I express the polynomial $G' = A(G)$ as a graph obeying $L(G') \equiv A(L(G))$. I use polynomials as an example because a polynomial of a symmetric matrix is, too, symmetric, and $[L(G'), L(G)] = 0$ necessarily holds. In some sense, we could (?) say $[G,G']=0$. My question doesn't specifically relate to which transformations apply, but to whether it would be correct to express manipulations of graphs in this way? Also, if anyone is familiar with this being used in previous research?

As far as I'm aware, the positive semidefinite nature does not apply on weighted graphs. For example, unless im mistaken, a tight binding Hamiltonian is, effectively, a laplacian.

Hi @suvrit. I have now rewritten the question in a much more concise manner. I hope this clears anything up.

Multiplication of two different graphs on the "same" vertices is trickier. As two different symmetric matrices do not generally multiply to another symmetric matrix, the resulting matrix would describe, perhaps, a multigraph. That gets hairy. However, it is perfectly valid to add two graphs through the laplacians, and (A + B)^n would be valid. Thus, whilst L (A)L(B) and L(B)L(A) do not generally describe a graph, the sum of the two must for the n=2 case to hold.

Indeed, my confidence with the terminology is lacking, so I felt the need to explain. A bit too much maybe! The multiplication of a graph with itself results in a graph whose laplacian is the square of the original graph's laplacian. The entire algebra is defined through the laplacian - however, the focus is on the features that emerge in the graph in which the resulting laplacian represents. I have provided an example of how polynomials in a basic graph can describe more complicated structures, and that the spectrum of the resulting structures is thus polynomial in the original spectrum.

Note the interesting result in this is that the laplacian of the original chain has a set of eigenvalues - the polynomials of the nth neighbour graphs have an eigenspectrum corresponding to their polynomial over the original spectrum.

Edit: Added an animation showing a cycle graph under "nth nearest neighbour" polynomials. The first of these polynomials are: $M^0$, $M^1$, $M^2 - 2M^0$, $M^3 - 3M$, $M^4 - 4M^2 + 2M^0$. Higher polynomials were calculated with a simple recursion algorithm, which works by eliminating lower order polynomials according to the binomial expansion.