Publication:
A Characterization of Graphs With Interval Two-Step Graphs

Loading...
Thumbnail Image
Authors
Lundgren, J. Richard
Merz, Sarah K.
Maybee, John S.
Rasmussen, Craig W.
Subjects
Advisors
Date of Issue
1995
Date
Publisher
Norrth-Holland
Language
Abstract
One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. This problem originated in the work of Cohen on food webs. We consider it for the class of loopless symmetric digraphs. The competition graph of a symmetric digraph D is the two-step graph of the underlying graph H of D, denoted S2 (H). The two-step graph is also known as the neighborhood graph, and has been studied recently by Brigham and Dutton and by Boland, Brigham and Dutton. This work was motivated by a paper of Raychaudhuri and Roberts where they investigated symmetric digraphs with a loop at each vertex. Under these assumptions, the competition graph is the square of the underlying graph H without loops. Here we first consider forbidden subgraph characterizations of graphs with interval two-step graphs. Second, we characterize a large class of graphs with interval two-step graphs using the Gilmore-Hoffman characterization of interval graphs.
Type
Article
Description
Series/Report No
Department
Mathematics
Other Units
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Linear Algebra and its Applications, v. 217, 1995, pp. 203-223
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections