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
Distribution Statement : APPROVED FOR PUBLIC RELEASE