MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to collect a few examples of applications of line graphs in sciences other than mathematics. To be more precise: I am thinking of models where there is a clear conceptual added value in switching the paradigm from a description focused on agents (nodes) to a description focused on relations (edges).

I know: put it like this it sounds very much like I am thinking of anthropological/sociological models, and indeed they are the most natural I could come up with$^{*}$, but I do believe that similar ideas appear elsewhere, too, modulo considering graph operations/decorations that allow for more flexible descriptions.

Inter/transdisciplinary examples would be particularly appreciated.

$^{*}$ It is not by chance that line graphs were so much pushed by Frank Harary after all, of all possible graph theorists :)

share|cite|improve this question
Just a suggestion. Find a suitable interpretation of vertex/edge colorings. And then play with the fact that the chromatic index of a graph is the chromatic number of its line graph. – Jernej Mar 7 '13 at 11:08
That's exactly what I do not want, Jernej :) Of course, most of the graphs are already line graphs of some other graphs. Mine is not a mathematical question: it is, if you wish, an epistemological question. When do people working in other fields feel the need to introduce the (slightly non-standard, in their eyes) line-graph-based paradigm? All the examples of applications of graphs I'm aware of do not (at least not those in the soft sciences) make any use of graph theory, let alone applying theorems on coloring of graphs. Harary's sociological papers were a luminous exception, of course – Delio Mugnolo Mar 7 '13 at 11:29
Delio, can you cite one of these sociological papers? – Jernej Mar 12 '13 at 9:51

Consider a wireless adhoc network that can be modeled as a graph $G=(V,E)$. Two links $e, f \in E$ cannot be simultaneously active if they are incident to the same node. This type of interference is called primary interference. The graph that models this interference is the line graph of $G$. More details about this application can be found in my paper (at and the references therein.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.