Accession Number : AD0784021

Title :   A Class of Facet Producing Graphs for Vertex Packing Polyhedra.

Descriptive Note : Technical summary rept.,

Corporate Author : WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s) : Trotter,L. E. , Jr

Report Date : MAY 1974

Pagination or Media Count : 26

Abstract : The author examines a family F of regular graphs which properly generalizes cliques, holes and anti-holes. A characterization is given for members of F whose associated vertex packing polytope contains a facet which cannot be derived from any proper induced subgraph. Simple necessary and sufficient conditions are given for a graph in F to contain another as an induced subgraph; these conditions are used to show that the graphs in F satisfy the Strong Perfect Graph Conjecture. Complements of members of F are also studied and we show that if both a graph and its complement belong to F, then the graph is an odd hole or odd anti-hole. (Author)

Descriptors :   *GRAPHICS, CONVEX SETS, INEQUALITIES, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE