A Characterization of Graphs with Interval Two-Step Graphs

Abstract

One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. In this paper we consider this problem for the class of loopless symmetric digraphs. Here we first consider forbidden subgraph characterizations of graphs with interval two-step graphs. We then characterize a large class of graphs with interval two-step graphs, using the Fulkerson-Gross characterization of interval graphs. Interval graphs, Competition graphs, Step graphs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 14, 1993
Accession Number
ADA275652

Entities

People

  • Craig W. Rasmussen
  • J. R. Lundgren
  • John S. Maybee
  • Sarah K. Merz

Organizations

  • University of Colorado Boulder

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Colorado
  • Competition
  • Continents
  • Contracts
  • Geographic Regions
  • Intervals
  • Mathematics
  • Military Research
  • Schools
  • Security
  • Triangles
  • Universities

Fields of Study

  • Mathematics

Readers

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