# Accession Number:

## AD0699892

# Title:

## TWO CHARACTERIZATIONS OF PROPER CIRCULAR-ARC GRAPHS.

# Descriptive Note:

## Technical rept.,

# Corporate Author:

## STANFORD UNIV CALIF OPERATIONS RESEARCH HOUSE

# Personal Author(s):

# Report Date:

## 1969-08-01

# Pagination or Media Count:

## 119.0

# Abstract:

An unoriented, irreflexive graph G is a proper circular-arc graph if there exists a proper family F of circular arcs proper means no arc of F contains another and a 1-1 correspondence between the vertices of G and the circular arcs in F such that two distinct vertices of G are adjacent if and only if the corresponding circular arcs in F intersect. The family F is called a proper circular-arc model for G. The fundamental problem is Given a graph G, under what conditions can one construct a proper circular-arc model for G. Two characterizations of proper circular-arc graphs are given, one in terms of a circular property of the adjacency matrix and the other in terms of forbidden subgraphs like Kuratowskis famous characterization of planar graphs. Author

# Descriptors:

# Subject Categories:

- Theoretical Mathematics