5
$\begingroup$

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 :)

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Jernej
    Mar 7, 2013 at 11:08
  • $\begingroup$ 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 $\endgroup$ Mar 7, 2013 at 11:29
  • $\begingroup$ Delio, can you cite one of these sociological papers? $\endgroup$
    – Jernej
    Mar 12, 2013 at 9:51
  • $\begingroup$ say, this: wisdomofwhores.com/wp-content/uploads/2010/12/… or this: asu.edu/clas/csdc/events/pdf/moody.pdf $\endgroup$ Mar 12, 2013 at 19:06

1 Answer 1

4
$\begingroup$

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 http://link.springer.com/article/10.1007%2Fs11276-013-0680-z) and the references therein.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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