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):

Report Date:

1974-05-01

Pagination or Media Count:

26.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE