Accession Number : ADA018426

Title :   Distances in Orientations of Graphs.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Chvatal,V. ; Thomassen,G.

Report Date : AUG 1975

Pagination or Media Count : 28

Abstract : The authors prove that there is a function h(k) such that every undirected graph G admits an orientation H with the following property: if an edge uv belongs to a cycle of length k in G then uv or vu belongs to a directed cycle of length at most h(k) in H. Next, it is shown that every undirected bridgeless graph of radius r admits an orientation of radius at most (r sup 2)+ r, and this bound is best possible. The same problem is considered with radius replaced by diameter. Finally, it is shown that the problem of deciding whether an undirected graph admits an orientation of diameter (resp. radius) two belongs to a class of problems called NP-hard.

Descriptors :   *Graphics, Set theory, Network flows, Theorems

Subject Categories : Theoretical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE