Quasi-Cayley graphs and interconnection networks

A shortest path routing R of a graph is an assignment of each pair (u,v) of vertices to a shortest path R(u,v) connecting u and v. If each vertex is the internal vertex of the same number of paths in R then R is said to be uniform. Every quasi-Cayley graph (a graph with a regular subset on vertices in automorphism group) admits a uniform shortest path routing. It has been conjectured that every vertex-transitive graph admits a uniform shortest path routing. Shim, Siran and Zerovnik discover counterexamples to the conjecture. The speaker reviews results on quasi-Cayley graphs and introduces open problems of interconnection networks.