Path-Regular Graphs.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA091123

Entities

People

  • Danny Dolev
  • David W. Matula

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Channel Allocation
  • Communication Channels
  • Communication Networks
  • Computer Science
  • Computers
  • Contracts
  • Diameters
  • Engineering
  • Governments
  • Graph Theory
  • Linear Programming
  • Military Research
  • Networks
  • Symmetry
  • United States
  • United States Government
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.