5
$\begingroup$

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?
$\endgroup$
6
  • $\begingroup$ And what about the Cantor-Bendixson derivative of a point set? In the same vein, are there deep connections between perfect numbers, perfect sets, and perfect graphs.? $\endgroup$
    – bof
    Apr 11, 2021 at 0:18
  • $\begingroup$ And what about the derived subgroup of a group? $\endgroup$ Apr 11, 2021 at 0:25
  • 1
    $\begingroup$ Do you suggest that there is no connection at all? It seems to me that the mentioned authors had a connection in mind, but really this is my question (and I would be happy to learn there is no connection, as happy as with the converse). $\endgroup$ Apr 11, 2021 at 0:26
  • $\begingroup$ I don't know. I'll be as interested to get an authoritative answer as you are. I suspect that when $A$ is a derived $B$, it just means you get $A$ from $B$ by some well-defined procedure, but I'd like to hear from someone who actually knows. $\endgroup$ Apr 11, 2021 at 0:28
  • 3
    $\begingroup$ @GerryMyerson That is what I suspect, too. But the fact that some authors call them derivatives (not just derived) and denote them by $\delta G$ makes me unsure. $\endgroup$ Apr 11, 2021 at 0:31

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Nice, thank you! Equivalently, one may say that $\delta f$ lives on $G$ edges, right? Is there some benefit to seeing it as living on its line graph vertices? May it make further operations easier, like iterating the derivation? $\endgroup$ Apr 12, 2021 at 7:50
  • 1
    $\begingroup$ Yeah, I'd say it makes iterating easier. $\endgroup$
    – gmvh
    Apr 12, 2021 at 7:54
  • $\begingroup$ I just found a paper explaining just this, and using it precisely for iteration purposes, with the use of incidence matrices. See the details in the answer I posted below (too long for a comment). Thank you for your help! $\endgroup$ Apr 12, 2021 at 20:13
2
$\begingroup$

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!

$\endgroup$

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.