5
$\begingroup$

What are some subtle, or non-obvious applications of algebraic graph theory? Obviously it can be used to study anything directly involving graphs (for instance, the wikipedia page mentions synchronizability of networks), but I'm interested in places where one might not immediately think graph theory to be relevant.

$\endgroup$
  • $\begingroup$ Theoretical chemistry is a big one. You see a lot of papers on spectral graph theory to help study chemical compounds. Machine learning is another. Spectral clustering algorithms are based off the Laplacian matrix eigenvalues. Computer scientists also use it in load balancing algorithms. $\endgroup$ – ml0105 Aug 19 '15 at 3:02
  • 1
    $\begingroup$ Dynamical systems over graphs is another neat application. Henning Mortveit is one of the predominant experts in this field. You might want to look at his papers and textbook Sequential Dynamical Systems. en.wikipedia.org/wiki/Graph_dynamical_system $\endgroup$ – ml0105 Aug 19 '15 at 3:25
  • $\begingroup$ @ml0105 Oh that's interesting! I'd sorta-kinda seen that before, but didn't realize the extent of work there, or the applications. Definitely taking a look at the book. Thanks! $\endgroup$ – Scott Lawrence Aug 19 '15 at 3:55
  • $\begingroup$ 95% of the research in this area comes from the NDSSL at Virginia Tech. Christian Reidys, the other author on the text, is at the lab as of a few months ago. $\endgroup$ – ml0105 Aug 19 '15 at 4:01
  • $\begingroup$ Google's PageRank algorithm is another one. $\endgroup$ – Ashwin Ganesan Oct 10 '15 at 16:58
3
$\begingroup$

It is more likely to find subtle, nonobvious applications of algebraic graph theory to graph theory.
A celebrated early example is the Friendship Theorem

https://en.wikipedia.org/wiki/Friendship_graph#Friendship_theorem

which has a nice proof using the spectrum of the adjacency matrix.

More recently the critical groups of sandpiles on graphs are a major theory related to tropical geometry. There are strong analogies with Riemann-Roch theory of divisors on algebraic curves.

Graph Laplacians are of huge interest, and closely related to the previous example.

Spectral embedding of graphs in the plane is another nice use of the adjacency matrix.

In applications outside graph theory, the structure of a graph relevant to the problem is usually not a well-hidden fact. If you are looking for applications of algebraic graph theory to generally obvious graph structure such as chemical bonds, there is plenty of that.

$\endgroup$
1
$\begingroup$

One application of algebraic graph theory is the design and analysis of topologies of interconnection networks. The topologies that are used to connect processors in a supercomputer have a high degree of symmetry and are usually Cayley graphs. See the Wikipedia article on the Torus interconnect, a topology used in some of the supercomputers.

$\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.