DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# Accession Number:

## ADA091123

# Title:

## Path-Regular Graphs.

# Descriptive Note:

## Technical rept.,

# Corporate Author:

## STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

# Report Date:

## 1980-06-01

# Pagination or Media Count:

##
41.0

# 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 GxGx...xG 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. Author

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#