Line graphs called "graph derivatives": any intuition?

Question

Short version: in several papers, line graphs (and closely related graphs) are called graph derivatives or derived graphs; is there any intuition for such terminologies, in connection with the classical concept of derivative?

---

Full version of the question.

In a 1961 paper entitled Graph Derivatives, Gert Sabidussi defines the graph derivative $\delta G$ of a graph $G$; it is nothing but the nowadays classical line graph of $G$.

Similarly, in 1970, Lowell W. Beineke calls this graph the derived graph of $G$ in his paper entitled Characterizations of derived graphs.

In 2017, a PhD dissertation entitled Structures of Derived Graphs was awarded to Khawlah Hamad Alhulwah at Western Michigan University. A large part of this work is about line graphs, and it gives the following intuition: "a derived graph of G is a graph obtained from G by a graph operation of some type."

It however seems to me that Sabidussi and Beineke (and, probably, others) had in mind a deeper connection between line graphs and the classical concept of (function) derivative.

In another line of works, the derived graph of $G$ has the same vertices as $G$ but they are connected by an edge if the distance between them in $G$ is $2$. This terminology was introduced in the 2009 paper Bounds On The Second Stage Spectral Radius Of Graphs by Ayyaswamy, Balachandran and Kannan, and further studied for instance in the 2012 paper Derived graphs of some graphs by Jog, Hande, Gutman, and Bozkurt. However, I can't find any explanation for this terminology in these papers.

My questions are:

• is there any reason to call line graphs graph derivatives? are they related to some extension of classical derivatives in a way that I miss?
• are there other definitions of graph derivatives that may be seen as such extensions?

Answer 1

If one considers a graph $G=(V,E)$ and a function $f:V\to\mathbb{R}$, it makes sense to look at the finite differences $f(v_i)-f(v_j)$ for neighboring vertices $v_i,v_j\in V$ as a sort of discrete derivative of $f$ (strictly speaking, this makes sense only for a directed graph, otherwise the sign isn't defined). If the graph is a discrete approximation (e.g. a triangulation or some sort of lattice) of some manifold, then this can be seen as a discretization of $\partial f$ (after weighting by edge length). The line graph is then the graph on whose vertices these discrete derivatives live, so it makes sense to see it as a sort of derivative of $G$ itself.

Answer 2

I just found the answer to this question in the paper Synthesis and analysis in total variation regularization by Francesco Ortelli and Sara van de Geer.

In the abstract, they write "We give a definition of the discrete graph derivative operator based on the notion of line graph", and they do so in Section 1.2. They use (a directed version of) the incidence matrix of a (directed) graph, and notice it may be used to differentiate a signal on the vertices of the graph along its edges, like gmvh suggests in the answer above. Then, in order to iterate such derivations, they introduce the (directed) line graph and say:

The idea behind using the line graph is the following: when computing differences along the direction of the graph, we obtain a value for each edge of the graph. Since we follow the direction of the edges, these values represent the first discrete derivative of the signal with respect to the graph, and constitute the vertices of the line graph.

They finally define the k-th order discrete graph derivative operator from the incidence matrix of iterated line graphs (meaning that they take the line graph of the line graph of the line graph etc).

It turns out that yes, line graphs and derivatives are strongly related!