Distances in Orientations of Graphs.

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.

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1975
Accession Number
ADA018426

Entities

People

  • G. Thomassen
  • V. Chvatal

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Cooperation
  • Diameters
  • Geometry
  • Group Dynamics
  • Mathematics
  • Optimization
  • Orientation (Direction)
  • Physical Properties

Readers

  • Graph Algorithms and Convex Optimization.