BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-80-807
       ENTRY:: June 08, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Path-regular graphs
        TYPE:: Technical Report
      AUTHOR:: Matula, David W.
      AUTHOR:: Dolev, Danny
        DATE:: June 1980
       PAGES:: 42
    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.
       NOTES:: [Adminitrivia V1/Prg/19950608]
         END:: STAN//CS-TR-80-807