Edit: The views/answers ratio on this question tells me that it was too long. As such, I've stripped out examples and now ask the question in brief. For examples, please ask in the comments or look at the previous revision of this question.

The question:

Consider some operation that maps the set of $n \times n$ symmetric matrices onto into itself $S: \text{sym}_n \rightarrow \text{sym}_n$. Examples include polynomials of a symmetric matrix etc (and, as a result, other functions such as sin and cos).

If we use such an operation on the laplacian $L(G)$ of a graph $G$ (with weighted vertices and edges), the result is a matrix that should also describe a variation of $G$ but with different vertex weights and edges. As such, we can define an operation which maps a graph onto another, by proxy. $\tilde{S}: G \rightarrow \tilde{S}(G), ~ L(\tilde{S}(G)) \equiv S(L(G)).$

For the example of a polynomial $S(L(G)) = \sum_i a_i (L(G))$, the spectrum of $L(\tilde{S}(G))$ can be easily found by applying the same polynomial to each eigenvalue of $L(G)$. Polynomials of some simple graphs can in fact be very interesting, and the eigenspectrum of such graphs can be found simply by finding the spectrum of $L(G)$.

Is anybody aware of any books or papers which explore such operations on graphs? I have been looking for some kind of study or reference for this, but to no avail. I have found such graph mappings very useful in some physics research, but I want to make sure it's (a) consistent and (b) not re-inventing the wheel.

Edit: The views/answers ratio on this question tells me that it was too long. As such, I've stripped out examples and now ask the question in brief. For examples, please ask in the comments or look at the previous revision of this question.

The question:

Consider some operation that maps the set of $n \times n$ symmetric matrices onto into itself $S: \text{sym}_n \rightarrow \text{sym}_n$. Examples include polynomials of a symmetric matrix etc (and, as a result, other functions such as sin and cos).

If we use such an operation on the laplacian $L(G)$ of a graph $G$ (with weighted vertices and edges), the result is a matrix that should also describe a variation of $G$ but with different vertex weights and edges. As such, we can define an operation which maps a graph onto another, by proxy. $\tilde{S}: G \rightarrow \tilde{S}(G), ~ L(\tilde{S}(G)) \equiv S(L(G)).$

For the example of a polynomial $S(L(G)) = \sum_i a_i (L(G))^i$, the spectrum of $L(\tilde{S}(G))$ can be easily found by applying the same polynomial to each eigenvalue of $L(G)$. Polynomials of some simple graphs can in fact be very interesting, and the eigenspectrum of such graphs can be found simply by finding the spectrum of $L(G)$.

Is anybody aware of any books or papers which explore such operations on graphs? I have been looking for some kind of study or reference for this, but to no avail. I have found such graph mappings very useful in some physics research, but I want to make sure it's (a) consistent and (b) not re-inventing the wheel.

Background:

I'm a theoretical physics PhD student, and so I'm used to slightly different notation and terminology, but I will do my best to pose this question correctly.

The following relates to a few interesting findings I've had in tight-binding models of 1d and 2d physical systems, but it's based upon an algebra over graphs which naturally fell out in my scribblings a few days ago. I cannot find this kind of graph algebra elsewhere; there has been no lack of trying in that regard. It isn't exactly deep in graph theory, but I've found it interesting, and I'm looking for existing work and advice. Here goes.

Summary of the question

Consider the operations $S: \text{sym}_n \rightarrow \text{sym}_n$ which map a symmetric matrix $L_1 \in \text{sym}_n$ to another symmetric matrix $L_2 \in \text{sym}_n$ operating on the same Hilbert space. If $L_1$ is the laplacian of an undirected graph with weighted edges and vertices, then it is reasonable to suggest that $L_2$ does is the laplacian of another such graph, but with different edges and different vertex weights. We can describe equivalent operations $\tilde{S}$ acting upon the graphs themselves, and explore the properties of these graphs.

  Examples include polynomials $\mathbb{R}[L_1]$ of symmetric matrices, and this can be extended to encompass taylor expansions of some functions such as $\sin$ and $\cos$, and in a sense we should be free to discuss something like $\sin(G)$ of a graph $G$.

To what extent has such an algebra been explored? Are there any obvious limitations or flaws in this?

The question in its entirety

Let $G(E,V)$ be a undirected graph with weighted edges $E$ and weighted vertices $V$, and denote $L(G) \in \text{sym}_{|V|}$ as the laplacian matrix corresponding to $G$.

Consider the operations which map $L(G)$ to another symmetric matrix. These operations include multiplication of matrices ($L(G)^n \in \text{sym}_{|V|} ~ \forall ~ n \in \mathbb{N}$) and addition of matrices / multiplication by real numbers ($rL(G) \in \text{sym}_{|V|} ~ \forall ~ r \in \mathbb{R}$). Putting these two operations together, we can then describe polynomials of the laplacian, $\mathbb{R}[L(G)] \in \text{sym}_{|V|}$. Let $p$ be such a polynomial. As $[G, p(G)] = 0$, for each eigenvalue/eigenstate pair $\lambda \in \mathbb{R}$ and $v \in \mathbb{C}^{|V|}$ with $L(G)v = \lambda v$, $L(p(G))v = p(\lambda)v$.

Rather than speaking of the operations as acting upon the laplacian, I wish to speak of them as acting on the graph itself. Put simply, $\forall s: \text{sym}_{|V|} \rightarrow \text{sym}_{|V|}, \exists ~ \tilde{s}: G(E,V) \rightarrow G'(E',V')$ obeying $L(\tilde{s}(G)) = s(L(G))$, and such that $V'$ corresponds to $V$ but with differing vertex weights (there needn't be any such relationship between the edges). In the crystal lattice setting, $V$ corresponds to the Hilbert space of lattice sites, and so $V$ and $V'$ are precisely the same bases in the same Hilbert space, and we haven't broken any rules. In the same way we define the polynomials of $L(G)$, we can define a polynomial of the graph itself, $\mathbb{R}[G]$.

There can also be other operations. These include the sum of two graphs with the same vertex set, a direct sum of graphs, an outer product of graphs (the latter two I know are already well established), polynomials over the sums of two graphs, and possibly much more.

I'm wondering if this has been explored before and, if so, to what extent. I would highly appreciate any resources related to this, and (possibly an unusual request) a criticism of my notation and terminology, so I don't make a fool out of myself in any further discussions!

What follows is a brief exploration of the polynomials, and, later, what I find to be a nice example in a physics setting.

Consider a weighted cycle graph $G = C_{14}$ with all vertices having weight 0 and all edges having unit weight. (Image crudely adapted from https://en.wikipedia.org/wiki/File:Heawood_Graph.svg)

We can automatically see that the structure of the laplacian obeys $L(G)_{ij} = \delta_{i, j+1 \pmod{14}} + \delta_{j, i + 1 \pmod{14}}$.

If we take the zeroth power of this graph (according to $L(G^0) = L(G)^0$), we get the following graph:

And in $G^2$, we find that edges exist between every other vertex and the vertices gain a weight of 2 (Excuse the mess):

So far, nothing really that interesting. $G^n$ simply comprises (multiplicative) walks of along $n$ edges, where a vertex obtains a weight given by the sum of the (multiplicative) walks that end up back at itself. In the case that vertices have a weight in $G$, the walk can stay on the vertex (so it can be imagined as an edge from each vertex to itself). Going futher, we can say some general things about bipartite graphs - notably, vertices do not obtain weights under odd powers. Under even powers, the graph is separable into two graphs.

So these are just monomials of $G$. The use of polynomials open up an interesting idea - we can remove the weights from the vertices in $G^2$ by subtracting $2G^0$. The result is a graph $G^2 - 2G^0$ of "next-nearest-only" edges (defined here as walks along 2 edges, forbidding all walks that start and end at the same vertex), without any effects in the laplacian from the vertex weights.

Looking at the third power, the following graph emerges (if you thought the last one was badly drawn, look away):

Where the edges between nearest neighbours are of weight 3 (as there are three 3-edge walks between such neighbours) and the edges between vertices of distance 3 (in G) are of unit weight. One can obtain 3rd-nearest-neighbour-only edges by the polynomial $G^3 - 3G$.

In general, on a graph corresponding to $C_N$, one can see that weight of the edge between vertex $i$ and vertex $i - n + 2k$ in $G^n$ is given by $\begin{pmatrix} n \\ k \end{pmatrix}$, $n < \frac{N}{2}$. As such, we can extract a polynomial to produce each nth-neighbour only graph based on $G$. For other graphs, there exist very different such polynomials. In a graph which alternates edge weights between 1 and $-1$, the edge weights in the various powers of the graph follow a modified Pascal's triangle, where the signs of elements alternate. I have also found polynomials describing nth-neighbour graphs for the honeycomb lattice graph and square lattice.

Edit: As an example of the "nth neighbour" polynomials in action, here is a short animation of a cycle graph under the first 36 such polynomials. For each power $n$, there exist polynomials whose highest power is $n$, which subtract the lower powers in such a way that only the nth-nearest neighbour edges remain.

There is some relevance to condensed matter, and I think it makes sense to give a very basic example. Let $H$ be a honeycomb lattice graph. The $L(H)$ corresponds to the nearest-neighbour tight binding hamiltonian of graphene. We can describe a "next-nearest neighbour" graph (comprising the original vertices and the set of edges between vertices of distance 2) with $H^2 - 3H^0$, and thus the eigenvalues of such a graph are related to each eigenvalue $\lambda$ of $L(H)$ by $\lambda^2 - 3$. Let $t \in \mathbb{R}$ and $t \in \mathbb{R}$ correspond to the hopping parameters between nearest and next-nearest neighbours in the honeycomb, then the combined corresponding graph is $tH + t'(H^2 - 3H^0)$, and each eigenvalue $\lambda$ of $L(H)$ are transformed as $t\lambda + t'(\lambda^2 - 3)$. As it turns out, the relationship between the crystal-momentum energies (laplacian eigenvalues) of the lattice corresponding to $tH$ transform exactly in this way in the next-nearest model (this is still a large approximation to the real system, but it's interesting).

Third-nearest neighbour interactions aren't quite as easy to extract, because not all walks of length 3 from a given vertex are at the same physical distance (and are related differently) in the real system. However, there is something new (or at least, something that I haven't found being noted) in the next-nearest-neighbour graphene tight binding model - the eigenvalues (and eigenstates, as they remain unchanged) can be calculated simply with some algebra and the nearest-neighbour states. Various lattice graphs can be taken to higher powers and exploited with other polynomials to extract energies to some nth-neighbour interaction.

There are many interesting features that emerge when systems and their polynomials are investigated under certain conditions. Examples include the square of the Hofstadter butterfly coming from triangular lattices with onsite energy 3 (the graphene lattice "squared" produces a direct sum of two of these), and it could lead to a possible classification of lattice structures based on the other structures that emerge under the polynomials, and a comparison between systems related in this manner.

Edit: The views/answers ratio on this question tells me that it was too long. As such, I've stripped out examples and now ask the question in brief. For examples, please ask in the comments or look at the previous revision of this question.

The question:

Consider some operation that maps the set of $n \times n$ symmetric matrices onto into itself $S: \text{sym}_n \rightarrow \text{sym}_n$. Examples include polynomials of a symmetric matrix etc (and, as a result, other functions such as sin and cos).

If we use such an operation on the laplacian $L(G)$ of a graph $G$ (with weighted vertices and edges), the result is a matrix that should also describe a variation of $G$ but with different vertex weights and edges. As such, we can define an operation which maps a graph onto another, by proxy. $\tilde{S}: G \rightarrow \tilde{S}(G), ~ L(\tilde{S}(G)) \equiv S(L(G)).$

For the example of a polynomial $S(L(G)) = \sum_i a_i (L(G))$, the spectrum of $L(\tilde{S}(G))$ can be easily found by applying the same polynomial to each eigenvalue of $L(G)$. Polynomials of some simple graphs can in fact be very interesting, and the eigenspectrum of such graphs can be found simply by finding the spectrum of $L(G)$.

Is anybody aware of any books or papers which explore such operations on graphs? I have been looking for some kind of study or reference for this, but to no avail. I have found such graph mappings very useful in some physics research, but I want to make sure it's (a) consistent and (b) not re-inventing the wheel.

Edit: As an example of the "nth neighbour" polynomials in action, here is a short animation of a cycle graph under the first 36 such polynomials. For each power $n$, there exist polynomials whose highest power is $n$, which subtract the lower powers in such a way that only the nth-nearest neighbour edges remain.