Report Number: CS-TR-80-807
Institution: Stanford University, Department of Computer Science
Title: Path-regular graphs
Author: Matula, David W.
Author: Dolev, Danny
Date: June 1980
Abstract: A graph is vertex-[edge-]path-regular if a list of shortest paths, allowing multiple copies of paths, exists where every pair of vertices are the endvertices of the same number of paths and each vertex [edge] occurs in the same number of paths of the list. The dependencies and independencies between the various path-regularity, regularity of degree, and symmetry properties are investigated. We show that every connected vertex-[edge-]symmetric graph is vertex-[edge-]path-regular, but not conversely. We show that the product of any two vertex-path-regular graphs is vertex-path-regular but not conversely, and the iterated product G x G x ... x G is edge-path-regular if and only if G is edge-path-regular. An interpretation of path-regular graphs is given regarding the efficient design of concurrent communication networks.
http://i.stanford.edu/pub/cstr/reports/cs/tr/80/807/CS-TR-80-807.pdf