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) : Tucker,Alan C.
Report Date : AUG 1969
Pagination or Media Count : 119
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 Kuratowski's famous characterization of planar graphs). (Author)
Descriptors : (*GRAPHICS, COMBINATORIAL ANALYSIS), GENETICS, SET THEORY, GEOMETRY, THEOREMS, THESES
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE